tdb/common/traverse.c

説明を見る。
00001  /* 
00002    Unix SMB/CIFS implementation.
00003 
00004    trivial database library
00005 
00006    Copyright (C) Andrew Tridgell              1999-2005
00007    Copyright (C) Paul `Rusty' Russell              2000
00008    Copyright (C) Jeremy Allison                    2000-2003
00009    
00010      ** NOTE! The following LGPL license applies to the tdb
00011      ** library. This does NOT imply that all of Samba is released
00012      ** under the LGPL
00013    
00014    This library is free software; you can redistribute it and/or
00015    modify it under the terms of the GNU Lesser General Public
00016    License as published by the Free Software Foundation; either
00017    version 2 of the License, or (at your option) any later version.
00018 
00019    This library is distributed in the hope that it will be useful,
00020    but WITHOUT ANY WARRANTY; without even the implied warranty of
00021    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00022    Lesser General Public License for more details.
00023 
00024    You should have received a copy of the GNU Lesser General Public
00025    License along with this library; if not, write to the Free Software
00026    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00027 */
00028 
00029 #include "tdb_private.h"
00030 
00031 /* Uses traverse lock: 0 = finish, -1 = error, other = record offset */
00032 static int tdb_next_lock(struct tdb_context *tdb, struct tdb_traverse_lock *tlock,
00033                          struct list_struct *rec)
00034 {
00035         int want_next = (tlock->off != 0);
00036 
00037         /* Lock each chain from the start one. */
00038         for (; tlock->hash < tdb->header.hash_size; tlock->hash++) {
00039                 if (!tlock->off && tlock->hash != 0) {
00040                         /* this is an optimisation for the common case where
00041                            the hash chain is empty, which is particularly
00042                            common for the use of tdb with ldb, where large
00043                            hashes are used. In that case we spend most of our
00044                            time in tdb_brlock(), locking empty hash chains.
00045                            
00046                            To avoid this, we do an unlocked pre-check to see
00047                            if the hash chain is empty before starting to look
00048                            inside it. If it is empty then we can avoid that
00049                            hash chain. If it isn't empty then we can't believe
00050                            the value we get back, as we read it without a
00051                            lock, so instead we get the lock and re-fetch the
00052                            value below.
00053                            
00054                            Notice that not doing this optimisation on the
00055                            first hash chain is critical. We must guarantee
00056                            that we have done at least one fcntl lock at the
00057                            start of a search to guarantee that memory is
00058                            coherent on SMP systems. If records are added by
00059                            others during the search then thats OK, and we
00060                            could possibly miss those with this trick, but we
00061                            could miss them anyway without this trick, so the
00062                            semantics don't change.
00063                            
00064                            With a non-indexed ldb search this trick gains us a
00065                            factor of around 80 in speed on a linux 2.6.x
00066                            system (testing using ldbtest).
00067                         */
00068                         tdb->methods->next_hash_chain(tdb, &tlock->hash);
00069                         if (tlock->hash == tdb->header.hash_size) {
00070                                 continue;
00071                         }
00072                 }
00073 
00074                 if (tdb_lock(tdb, tlock->hash, tlock->lock_rw) == -1)
00075                         return -1;
00076 
00077                 /* No previous record?  Start at top of chain. */
00078                 if (!tlock->off) {
00079                         if (tdb_ofs_read(tdb, TDB_HASH_TOP(tlock->hash),
00080                                      &tlock->off) == -1)
00081                                 goto fail;
00082                 } else {
00083                         /* Otherwise unlock the previous record. */
00084                         if (tdb_unlock_record(tdb, tlock->off) != 0)
00085                                 goto fail;
00086                 }
00087 
00088                 if (want_next) {
00089                         /* We have offset of old record: grab next */
00090                         if (tdb_rec_read(tdb, tlock->off, rec) == -1)
00091                                 goto fail;
00092                         tlock->off = rec->next;
00093                 }
00094 
00095                 /* Iterate through chain */
00096                 while( tlock->off) {
00097                         tdb_off_t current;
00098                         if (tdb_rec_read(tdb, tlock->off, rec) == -1)
00099                                 goto fail;
00100 
00101                         /* Detect infinite loops. From "Shlomi Yaakobovich" <Shlomi@exanet.com>. */
00102                         if (tlock->off == rec->next) {
00103                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_next_lock: loop detected.\n"));
00104                                 goto fail;
00105                         }
00106 
00107                         if (!TDB_DEAD(rec)) {
00108                                 /* Woohoo: we found one! */
00109                                 if (tdb_lock_record(tdb, tlock->off) != 0)
00110                                         goto fail;
00111                                 return tlock->off;
00112                         }
00113 
00114                         /* Try to clean dead ones from old traverses */
00115                         current = tlock->off;
00116                         tlock->off = rec->next;
00117                         if (!(tdb->read_only || tdb->traverse_read) && 
00118                             tdb_do_delete(tdb, current, rec) != 0)
00119                                 goto fail;
00120                 }
00121                 tdb_unlock(tdb, tlock->hash, tlock->lock_rw);
00122                 want_next = 0;
00123         }
00124         /* We finished iteration without finding anything */
00125         return TDB_ERRCODE(TDB_SUCCESS, 0);
00126 
00127  fail:
00128         tlock->off = 0;
00129         if (tdb_unlock(tdb, tlock->hash, tlock->lock_rw) != 0)
00130                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_next_lock: On error unlock failed!\n"));
00131         return -1;
00132 }
00133 
00134 /* traverse the entire database - calling fn(tdb, key, data) on each element.
00135    return -1 on error or the record count traversed
00136    if fn is NULL then it is not called
00137    a non-zero return value from fn() indicates that the traversal should stop
00138   */
00139 static int tdb_traverse_internal(struct tdb_context *tdb, 
00140                                  tdb_traverse_func fn, void *private_data,
00141                                  struct tdb_traverse_lock *tl)
00142 {
00143         TDB_DATA key, dbuf;
00144         struct list_struct rec;
00145         int ret, count = 0;
00146 
00147         /* This was in the initializaton, above, but the IRIX compiler
00148          * did not like it.  crh
00149          */
00150         tl->next = tdb->travlocks.next;
00151 
00152         /* fcntl locks don't stack: beware traverse inside traverse */
00153         tdb->travlocks.next = tl;
00154 
00155         /* tdb_next_lock places locks on the record returned, and its chain */
00156         while ((ret = tdb_next_lock(tdb, tl, &rec)) > 0) {
00157                 count++;
00158                 /* now read the full record */
00159                 key.dptr = tdb_alloc_read(tdb, tl->off + sizeof(rec), 
00160                                           rec.key_len + rec.data_len);
00161                 if (!key.dptr) {
00162                         ret = -1;
00163                         if (tdb_unlock(tdb, tl->hash, tl->lock_rw) != 0)
00164                                 goto out;
00165                         if (tdb_unlock_record(tdb, tl->off) != 0)
00166                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_traverse: key.dptr == NULL and unlock_record failed!\n"));
00167                         goto out;
00168                 }
00169                 key.dsize = rec.key_len;
00170                 dbuf.dptr = key.dptr + rec.key_len;
00171                 dbuf.dsize = rec.data_len;
00172 
00173                 /* Drop chain lock, call out */
00174                 if (tdb_unlock(tdb, tl->hash, tl->lock_rw) != 0) {
00175                         ret = -1;
00176                         SAFE_FREE(key.dptr);
00177                         goto out;
00178                 }
00179                 if (fn && fn(tdb, key, dbuf, private_data)) {
00180                         /* They want us to terminate traversal */
00181                         ret = count;
00182                         if (tdb_unlock_record(tdb, tl->off) != 0) {
00183                                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_traverse: unlock_record failed!\n"));;
00184                                 ret = -1;
00185                         }
00186                         SAFE_FREE(key.dptr);
00187                         goto out;
00188                 }
00189                 SAFE_FREE(key.dptr);
00190         }
00191 out:
00192         tdb->travlocks.next = tl->next;
00193         if (ret < 0)
00194                 return -1;
00195         else
00196                 return count;
00197 }
00198 
00199 
00200 /*
00201   a write style traverse - temporarily marks the db read only
00202 */
00203 int tdb_traverse_read(struct tdb_context *tdb, 
00204                       tdb_traverse_func fn, void *private_data)
00205 {
00206         struct tdb_traverse_lock tl = { NULL, 0, 0, F_RDLCK };
00207         int ret;
00208         
00209         /* we need to get a read lock on the transaction lock here to
00210            cope with the lock ordering semantics of solaris10 */
00211         if (tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_RDLCK, F_SETLKW, 0, 1) == -1) {
00212                 TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_traverse_read: failed to get transaction lock\n"));
00213                 tdb->ecode = TDB_ERR_LOCK;
00214                 return -1;
00215         }
00216 
00217         tdb->traverse_read++;
00218         ret = tdb_traverse_internal(tdb, fn, private_data, &tl);
00219         tdb->traverse_read--;
00220 
00221         tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_UNLCK, F_SETLKW, 0, 1);
00222 
00223         return ret;
00224 }
00225 
00226 /*
00227   a write style traverse - needs to get the transaction lock to
00228   prevent deadlocks
00229 */
00230 int tdb_traverse(struct tdb_context *tdb, 
00231                  tdb_traverse_func fn, void *private_data)
00232 {
00233         struct tdb_traverse_lock tl = { NULL, 0, 0, F_WRLCK };
00234         int ret;
00235 
00236         if (tdb->read_only || tdb->traverse_read) {
00237                 return tdb_traverse_read(tdb, fn, private_data);
00238         }
00239         
00240         if (tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_WRLCK, F_SETLKW, 0, 1) == -1) {
00241                 TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_traverse: failed to get transaction lock\n"));
00242                 tdb->ecode = TDB_ERR_LOCK;
00243                 return -1;
00244         }
00245 
00246         ret = tdb_traverse_internal(tdb, fn, private_data, &tl);
00247 
00248         tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_UNLCK, F_SETLKW, 0, 1);
00249 
00250         return ret;
00251 }
00252 
00253 
00254 /* find the first entry in the database and return its key */
00255 TDB_DATA tdb_firstkey(struct tdb_context *tdb)
00256 {
00257         TDB_DATA key;
00258         struct list_struct rec;
00259 
00260         /* release any old lock */
00261         if (tdb_unlock_record(tdb, tdb->travlocks.off) != 0)
00262                 return tdb_null;
00263         tdb->travlocks.off = tdb->travlocks.hash = 0;
00264         tdb->travlocks.lock_rw = F_RDLCK;
00265 
00266         /* Grab first record: locks chain and returned record. */
00267         if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0)
00268                 return tdb_null;
00269         /* now read the key */
00270         key.dsize = rec.key_len;
00271         key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
00272 
00273         /* Unlock the hash chain of the record we just read. */
00274         if (tdb_unlock(tdb, tdb->travlocks.hash, tdb->travlocks.lock_rw) != 0)
00275                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_firstkey: error occurred while tdb_unlocking!\n"));
00276         return key;
00277 }
00278 
00279 /* find the next entry in the database, returning its key */
00280 TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey)
00281 {
00282         u32 oldhash;
00283         TDB_DATA key = tdb_null;
00284         struct list_struct rec;
00285         char *k = NULL;
00286 
00287         /* Is locked key the old key?  If so, traverse will be reliable. */
00288         if (tdb->travlocks.off) {
00289                 if (tdb_lock(tdb,tdb->travlocks.hash,tdb->travlocks.lock_rw))
00290                         return tdb_null;
00291                 if (tdb_rec_read(tdb, tdb->travlocks.off, &rec) == -1
00292                     || !(k = tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),
00293                                             rec.key_len))
00294                     || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
00295                         /* No, it wasn't: unlock it and start from scratch */
00296                         if (tdb_unlock_record(tdb, tdb->travlocks.off) != 0) {
00297                                 SAFE_FREE(k);
00298                                 return tdb_null;
00299                         }
00300                         if (tdb_unlock(tdb, tdb->travlocks.hash, tdb->travlocks.lock_rw) != 0) {
00301                                 SAFE_FREE(k);
00302                                 return tdb_null;
00303                         }
00304                         tdb->travlocks.off = 0;
00305                 }
00306 
00307                 SAFE_FREE(k);
00308         }
00309 
00310         if (!tdb->travlocks.off) {
00311                 /* No previous element: do normal find, and lock record */
00312                 tdb->travlocks.off = tdb_find_lock_hash(tdb, oldkey, tdb->hash_fn(&oldkey), tdb->travlocks.lock_rw, &rec);
00313                 if (!tdb->travlocks.off)
00314                         return tdb_null;
00315                 tdb->travlocks.hash = BUCKET(rec.full_hash);
00316                 if (tdb_lock_record(tdb, tdb->travlocks.off) != 0) {
00317                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno)));
00318                         return tdb_null;
00319                 }
00320         }
00321         oldhash = tdb->travlocks.hash;
00322 
00323         /* Grab next record: locks chain and returned record,
00324            unlocks old record */
00325         if (tdb_next_lock(tdb, &tdb->travlocks, &rec) > 0) {
00326                 key.dsize = rec.key_len;
00327                 key.dptr = tdb_alloc_read(tdb, tdb->travlocks.off+sizeof(rec),
00328                                           key.dsize);
00329                 /* Unlock the chain of this new record */
00330                 if (tdb_unlock(tdb, tdb->travlocks.hash, tdb->travlocks.lock_rw) != 0)
00331                         TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
00332         }
00333         /* Unlock the chain of old record */
00334         if (tdb_unlock(tdb, BUCKET(oldhash), tdb->travlocks.lock_rw) != 0)
00335                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
00336         return key;
00337 }

Sambaに対してSat Aug 29 21:23:27 2009に生成されました。  doxygen 1.4.7