"Fossies" - the Fresh Open Source Software Archive

Member "coda-6.9.5/lib-src/rwcdb/rwcdb.c" (24 May 2006, 16233 Bytes) of package /linux/misc/old/coda-6.9.5.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "rwcdb.c" see the Fossies "Dox" file reference documentation.

    1 /* BLURB lgpl
    2 
    3                            Coda File System
    4                               Release 6
    5 
    6           Copyright (c) 2003 Carnegie Mellon University
    7                   Additional copyrights listed below
    8 
    9 This  code  is  distributed "AS IS" without warranty of any kind under
   10 the  terms of the  GNU  Library General Public Licence  Version 2,  as
   11 shown in the file LICENSE. The technical and financial contributors to
   12 Coda are listed in the file CREDITS.
   13 
   14                         Additional copyrights
   15 */
   16 
   17 #ifdef HAVE_CONFIG_H
   18 #include <config.h>
   19 #endif
   20 
   21 #include <sys/types.h>
   22 #include <sys/param.h>
   23 #include <sys/stat.h>
   24 #include <stdlib.h>
   25 #include <unistd.h>
   26 #include <string.h>
   27 #include <stdio.h>
   28 #include <fcntl.h>
   29 
   30 #include "rwcdb_pack.h"
   31 #include "rwcdb.h"
   32 
   33 /*=====================================================================*/
   34 /* some file related ops */
   35 
   36 static int owrite(struct rwcdb *c)
   37 {
   38     char newname[MAXPATHLEN];
   39 
   40     if (c->readonly) return -1;
   41     if (c->wf.fd != -1) return 0;
   42 
   43     strcpy(newname, c->file);
   44     strcat(newname, ".tmp");
   45 
   46     if (db_file_open(&c->wf, newname, O_CREAT | O_EXCL | O_WRONLY)) {
   47         fprintf(stderr, "RWCDB error: open %s failed, multiple writers?\n",
   48                 newname);
   49         return -1;
   50     }
   51     return 0;
   52 }
   53 
   54 static void discard_pending_updates(struct rwcdb *c);
   55 
   56 static void checkdb(struct rwcdb *c)
   57 {
   58     struct stat sb;
   59 
   60     /* reopen the database, but only if it has been modified */
   61     if (stat(c->file, &sb) != 0 || sb.st_ino == c->rf.ino)
   62     return;
   63 
   64     db_file_close(&c->rf);
   65     if (db_file_open(&c->rf, c->file, O_RDONLY)) {
   66     /* Ouch, we just hosed ourselves big time */
   67     abort();
   68     }
   69     c->index = 2048;
   70 
   71     discard_pending_updates(c);
   72 }
   73 
   74 /*=====================================================================*/
   75 /* wrentries are linked together to store pending updates in memory */
   76 
   77 struct wrentry {
   78     struct dllist_head list;
   79     u_int32_t hash;
   80     u_int32_t pos;
   81     u_int32_t klen;
   82     u_int32_t dlen;
   83 };
   84 
   85 /* behind the struct wrentry is a variable length area that contains key/data */
   86 #define wbuf(w) (((char *)w) + sizeof(struct wrentry) - 8)
   87 #define wkey(w) (wbuf(w) + 8)
   88 #define wdata(w) (wbuf(w) + 8 + (w)->klen)
   89 
   90 static struct wrentry *alloc_wrentry(const u_int32_t klen, const u_int32_t dlen,
   91                                      const u_int32_t hash)
   92 {
   93     struct wrentry *w;
   94 
   95     w = (struct wrentry *)malloc(sizeof(struct wrentry) + 8 + klen + dlen);
   96     if (!w) return NULL;
   97 
   98     w->hash = hash;
   99     w->klen = klen;
  100     w->dlen = dlen;
  101     return w;
  102 }
  103 
  104 static void free_wrentry(struct wrentry *w)
  105 {
  106     list_del(&w->list);
  107     free(w);
  108 }
  109 
  110 
  111 static struct wrentry *ispending(struct rwcdb *c, const char *k,
  112                                  const u_int32_t klen, const u_int32_t hash,
  113                                  u_int32_t *index)
  114 {
  115     struct dllist_head *p;
  116     struct wrentry *w;
  117     u_int32_t i, idx = 0;
  118 
  119     list_for_each(p, c->removed)
  120     {
  121         w = list_entry(p, struct wrentry, list); 
  122         if (w->hash == hash && klen == w->klen &&
  123             memcmp(wkey(w), k, klen) == 0) {
  124             return w;
  125         }
  126     }
  127 
  128     if (!c->hlens[hash & 0xff]) return NULL;
  129 
  130     if (index) {
  131         for (i = 0; i < (hash & 0xff); i++)
  132             idx += c->hlens[i];
  133     }
  134 
  135     list_for_each(p, c->added[hash & 0xff])
  136     {
  137         w = list_entry(p, struct wrentry, list); 
  138         if (w->hash == hash && klen == w->klen &&
  139             memcmp(wkey(w), k, klen) == 0)
  140         {
  141             if (index) *index = idx;
  142             return w;
  143         }
  144         idx++;
  145     }
  146     return NULL;
  147 }
  148 
  149 static struct wrentry *fromhash(struct rwcdb *c, u_int32_t index)
  150 {
  151     struct dllist_head *p;
  152     u_int32_t i;
  153 
  154     for (i = 0; i < 256; i++) {
  155         if (index >= c->hlens[i]) {
  156             index -= c->hlens[i];
  157             continue;
  158         }
  159         list_for_each(p, c->added[i])
  160         {
  161             if (index--) continue;
  162             return list_entry(p, struct wrentry, list);
  163         }
  164     }
  165     return NULL;
  166 }
  167 
  168 static void discard_pending_updates(struct rwcdb *c)
  169 {
  170     struct dllist_head *p;
  171     struct wrentry *w;
  172     u_int32_t i;
  173 
  174     /* discard left-over in-memory modifications */
  175     for (i = 0; i < 256; i++) {
  176         for (p = c->added[i].next; p != &c->added[i];) {
  177             w = list_entry(p, struct wrentry, list);
  178             p = p->next;
  179             free_wrentry(w);
  180         }
  181     }
  182     for (p = c->removed.next; p != &c->removed;) {
  183         w = list_entry(p, struct wrentry, list);
  184         p = p->next;
  185         free_wrentry(w);
  186     }
  187     memset(c->hlens, 0, 256 * sizeof(u_int32_t));
  188 }
  189 
  190 /*=====================================================================*/
  191 /* The cdb hash function is "h = ((h << 5) + h) ^ c", with a starting
  192  * hash of 5381 */
  193 
  194 static u_int32_t cdb_hash(const char *k, const u_int32_t klen)
  195 {
  196     u_int32_t i, hash = 5381;
  197 
  198     for (i = 0; i < klen; i++)
  199         hash = ((hash << 5) + hash) ^ ((unsigned char)k[i]);
  200 
  201     return hash;
  202 }
  203 
  204 /*=====================================================================*/
  205 /* main functions */
  206 
  207 int rwcdb_init(struct rwcdb *c, const char *file, const int mode)
  208 {
  209     u_int32_t i, n;
  210     
  211     n = strlen(file) + 1;
  212     if (n > MAXPATHLEN - 5) return -1;
  213 
  214     memset(c, 0, sizeof(struct rwcdb));
  215 
  216     c->file = strdup(file);
  217     if (!c->file) return -1;
  218 
  219     c->removed.next = c->removed.prev = &c->removed;
  220     for (i = 0; i < 256; i++)
  221         c->added[i].next = c->added[i].prev = &c->added[i];
  222 
  223     c->readonly = ((mode & O_ACCMODE) == O_RDONLY);
  224     c->rf.fd = c->wf.fd = -1;
  225     if (db_file_open(&c->rf, file, O_RDONLY) == 0)
  226         return 0;
  227     
  228     if (c->rf.fd != -1)
  229     goto err_out;
  230 
  231     /* try to create a new database */
  232     if (owrite(c) != -1 && rwcdb_sync(c) != -1)
  233         return 0;
  234 
  235     db_file_close(&c->wf);
  236 
  237 err_out:
  238     if (c->file) {
  239     free(c->file);
  240     c->file = NULL;
  241     }
  242     return -1;
  243 }
  244 
  245 int rwcdb_free(struct rwcdb *c)
  246 {
  247     if (rwcdb_sync(c) == -1)
  248         return -1;
  249 
  250     /* just in case someone was modifying a readonly database */
  251     discard_pending_updates(c);
  252 
  253     db_file_close(&c->rf);
  254 
  255     if (c->file) {
  256     free(c->file);
  257     c->file = NULL;
  258     }
  259     return 1;
  260 }
  261 
  262 int rwcdb_find(struct rwcdb *c, const char *k, const u_int32_t klen)
  263 {
  264     u_int32_t loop, hash, hash2, hpos, hlen, pos, keylen, cur_pos, dlen;
  265     struct wrentry *w;
  266     void *buf;
  267 
  268     /* A record is located as follows. Compute the hash value of the key in
  269      * the record. The hash value modulo 256 is the number of a hash table.
  270      * The hash value divided by 256, modulo the length of that table, is a
  271      * slot number. Probe that slot, the next higher slot, and so on, until
  272      * you find the record or run into an empty slot. */
  273     hash = cdb_hash(k, klen);
  274 
  275     /* first check whether there are pending modifications for this key */
  276     w = ispending(c, k, klen, hash, &loop);
  277     if (w) {
  278         if (!w->dlen) return 0;
  279         c->klen = w->klen;
  280         c->dlen = w->dlen;
  281         c->dpos = c->rf.eod + loop;
  282         return 1;
  283     }
  284 
  285     /* Each of the 256 initial pointers states a position and a length. The
  286      * position is the starting position of the hash table. The length is the
  287      * number of slots in the hash table. */
  288     cur_pos = (hash & 0xff) << 3;
  289     if (readints(&c->rf, &hpos, &hlen, cur_pos))
  290         return -1;
  291 
  292     /* micro-optimization? */
  293     if (hlen == 0) return 0;
  294 
  295     cur_pos = hpos + (((hash >> 8) % hlen) << 3);
  296 
  297     for (loop = 0; loop < hlen; loop++) {
  298         /* Each hash table slot states a hash value and a byte position. If
  299          * the byte position is 0, the slot is empty. Otherwise, the slot
  300          * points to a record whose key has that hash value. */
  301         if (readints(&c->rf, &hash2, &pos, cur_pos))
  302             return -1;
  303 
  304         if (pos == 0) return 0;
  305 
  306         cur_pos += 8;
  307         if (cur_pos == hpos + (hlen << 3))
  308             cur_pos = hpos;
  309 
  310         if (hash != hash2) continue;
  311 
  312         /* Records are stored sequentially, without special alignment. A
  313          * record states a key length, a data length, the key, and the data. */
  314         if (readints(&c->rf, &keylen, &dlen, pos))
  315             return -1;
  316 
  317         if (klen != keylen) continue;
  318 
  319         if (db_file_mread(&c->rf, &buf, klen + dlen, c->rf.pos))
  320             return -1;
  321 
  322         if (memcmp(k, buf, klen) == 0) {
  323             c->klen = klen;
  324             c->dlen = dlen;
  325             c->dpos = c->rf.pos - dlen;
  326             return 1;
  327         }
  328     }
  329     return 0;
  330 }
  331 
  332 int rwcdb_insert(struct rwcdb *c, const char *k, const u_int32_t klen,
  333                   const char *d, const u_int32_t dlen)
  334 {
  335     struct wrentry *w, *old;
  336     u_int32_t hash, slot;
  337     static u_int32_t warned = 0;
  338 
  339     if (c->readonly) {
  340     if (!warned++)
  341         fprintf(stderr, "RWCDB warning: modifying read-only database\n");
  342     }
  343     else if (owrite(c) == -1)
  344     return -1;
  345 
  346     hash = cdb_hash(k, klen);
  347     w = alloc_wrentry(klen, dlen, hash);
  348     if (!w) return -1;
  349 
  350     memcpy(wkey(w), k, klen);
  351     if (dlen) memcpy(wdata(w), d, dlen);
  352 
  353     old = ispending(c, k, klen, hash, NULL);
  354 
  355     slot = hash & 0xff;
  356     if (old) {
  357         if (old->dlen)
  358             c->hlens[slot]--;
  359         free_wrentry(old);
  360     }
  361 
  362     if (dlen) {
  363         list_add(&w->list, c->added[slot].prev);
  364         c->hlens[slot]++;
  365     } else
  366         list_add(&w->list, c->removed.prev);
  367 
  368     return 1;
  369 }
  370 
  371 int rwcdb_delete(struct rwcdb *c, const char *k, const u_int32_t klen)
  372 {
  373     if (rwcdb_find(c, k, klen) != 1) return 0;
  374     return rwcdb_insert(c, k, klen, NULL, 0);
  375 }
  376 
  377 int rwcdb_next(struct rwcdb *c, int init)
  378 {
  379     u_int32_t klen, dlen, hash;
  380     void *buf;
  381 
  382     if (init) c->index = 2048;
  383 
  384 again:
  385     /* reading from disk? */
  386     if (c->index < c->rf.eod) {
  387         if (readints(&c->rf, &klen, &dlen, c->index))
  388             goto read_failed;
  389 
  390         if (db_file_mread(&c->rf, &buf, klen + dlen, c->rf.pos))
  391             goto read_failed;
  392 
  393         hash = cdb_hash(buf, klen);
  394         c->pending = ispending(c, buf, klen, hash, NULL);
  395 
  396         c->index = c->rf.pos;
  397 
  398         /* already on the write queue? skip entry */
  399         if (c->pending) goto again;
  400 
  401         c->hash = hash;
  402         c->klen = klen;
  403         c->dlen = dlen;
  404         c->dpos = c->rf.pos - dlen;
  405         return 1;
  406     }
  407 
  408     /* sweep through the pending write hashes */
  409     c->pending = fromhash(c, c->index - c->rf.eod);
  410     if (!c->pending) return 0;
  411 
  412     c->klen = c->pending->klen;
  413     c->dlen = c->pending->dlen;
  414     c->dpos = c->index;
  415 
  416     c->index++;
  417     return 1;
  418 
  419 read_failed:
  420     fprintf(stderr, "RWCDB rwcdb_next: read failed, %s corrupt?\n", c->file);
  421     return -1;
  422 }
  423 
  424 int rwcdb_read(struct rwcdb *c, char *d, const u_int32_t dlen,
  425                const u_int32_t dpos)
  426 {
  427     struct wrentry *w;
  428     void *buf;
  429 
  430     /* still reading on-disk information? */
  431     if (dpos < c->rf.eod) {
  432         if (db_file_mread(&c->rf, &buf, dlen, dpos))
  433             return -1;
  434     } else {
  435         /* sweep through the pending write hashes */
  436         w = fromhash(c, dpos - c->rf.eod);
  437         if (!w || dlen > w->dlen) return -1;
  438         buf = wdata(w);
  439     }
  440     memcpy(d, buf, dlen);
  441 
  442     return 0;
  443 }
  444 
  445 int rwcdb_readkey(struct rwcdb *c, char *k, const u_int32_t klen,
  446                   const u_int32_t dpos)
  447 {
  448     struct wrentry *w;
  449     void *buf;
  450 
  451     if (dpos < c->rf.eod) {
  452         if (db_file_mread(&c->rf, &buf, klen, dpos - klen))
  453             return -1;
  454     } else {
  455         /* sweep through the pending write hashes */
  456         w = fromhash(c, dpos - c->rf.eod);
  457         if (!w || klen != w->klen) return -1;
  458         buf = wkey(w);
  459     }
  460     memcpy(k, buf, klen);
  461 
  462     return 0;
  463 }
  464 
  465 /*=====================================================================*/
  466 /* writing new databases */
  467 
  468 static int dump_records(struct rwcdb *c, struct dllist_head *old)
  469 {
  470     int ret, rewind = 1;
  471     struct wrentry *w;
  472     char ints[8];
  473     void *buf;
  474 
  475     while(1) {
  476         ret = rwcdb_next(c, rewind);
  477         if (ret != 1) return ret;
  478         rewind = 0;
  479 
  480         if (!c->pending) {
  481             w = alloc_wrentry(0, 0, c->hash);
  482             if (!w) {
  483                 fprintf(stderr, "RWCDB dump_records: allocation failed?\n");
  484                 return -1;
  485             }
  486             list_add(&w->list, old->prev);
  487             if (db_file_mread(&c->rf, &buf, c->klen+c->dlen, c->dpos - c->klen))
  488                 return -1;
  489         }
  490         else {
  491             w = c->pending;
  492             buf = wkey(w);
  493         }
  494 
  495         /* store position of this record */
  496         w->pos = c->wf.pos;
  497 
  498         packints(ints, c->klen, c->dlen);
  499 
  500         if (db_file_write(&c->wf, ints, 8) ||
  501             db_file_write(&c->wf, buf, c->klen+c->dlen)) {
  502             fprintf(stderr, "RWCDB dump_records: write failed, out of diskspace?\n");
  503             return -1;
  504         }
  505     }
  506     return 0;
  507 }
  508 
  509 static int write_hashchains(struct rwcdb *c)
  510 {
  511     u_int32_t i, slot, hoffs[256], len, maxlen, totallen;
  512     struct wrentry *w;
  513     struct dllist_head *p;
  514     struct rwcdb_tuple *h;
  515 
  516     maxlen = 256; totallen = 0;
  517     for (i = 0; i < 256; i++) {
  518         len = c->hlens[i] * 2;
  519         if (len > maxlen) maxlen = len;
  520         totallen += len;
  521     }
  522 
  523     h = (struct rwcdb_tuple *)malloc(maxlen * sizeof(struct rwcdb_tuple));
  524     if (!h) {
  525         fprintf(stderr, "RWCDB write_hashchains: allocation failed\n");
  526         return -1;
  527     }
  528 
  529     for (i = 0; i < 256; i++) {
  530         len = c->hlens[i] * 2;
  531         hoffs[i] = c->wf.pos;
  532         if (len == 0) continue;
  533 
  534         memset(h, 0, len * sizeof(struct rwcdb_tuple));
  535 
  536         list_for_each(p, c->added[i]) {
  537             w = list_entry(p, struct wrentry, list);
  538             slot = (w->hash >> 8) % len;
  539             while (h[slot].a) {
  540                 if (++slot == len)
  541                     slot = 0;
  542             }
  543             packints((char *)&h[slot], w->hash, w->pos);
  544         }
  545 
  546         if (db_file_write(&c->wf, h, len * sizeof(struct rwcdb_tuple)))
  547             goto write_failed;
  548     }
  549 
  550     /* dump the header */
  551     for (i = 0; i < 256; i++)
  552         packints((char *)(&h[i]), hoffs[i], c->hlens[i] * 2);
  553     if (db_file_flush(&c->wf) ||
  554         db_file_seek(&c->wf, 0) ||
  555         db_file_write(&c->wf, h, 256 * sizeof(struct rwcdb_tuple)) ||
  556         db_file_flush(&c->wf))
  557         goto write_failed;
  558 
  559     free(h);
  560     return 0;
  561 
  562 write_failed:
  563     fprintf(stderr, "RWCDB rwcdb_write_hashchains: write failed, out of diskspace?\n");
  564     free(h);
  565     return -1;
  566 }
  567 
  568 int rwcdb_sync(struct rwcdb *c)
  569 {
  570     u_int32_t i;
  571     struct dllist_head *p, rewrites;
  572     struct wrentry *w;
  573     char newname[MAXPATHLEN];
  574 
  575     if (c->wf.fd == -1) {
  576         /* see if the on-disk database was updated */
  577         checkdb(c);
  578         return 1;
  579     }
  580 
  581     rewrites.prev = rewrites.next = &rewrites;
  582 
  583     if (db_file_seek(&c->wf, 2048))
  584         return -1;
  585 
  586     if (dump_records(c, &rewrites))
  587         goto recover;
  588 
  589     /* remember EOD */
  590     c->wf.eod = c->wf.pos;
  591 
  592     /* move rewritten entries into the hashlists */
  593     for (p = rewrites.next; p != &rewrites;) {
  594         w = list_entry(p, struct wrentry, list);
  595         p = p->next;
  596         list_del(&w->list);
  597         list_add(&w->list, &c->added[w->hash & 0xff]);
  598         c->hlens[w->hash & 0xff]++;
  599     }
  600 
  601     /* dump hash chains and header */
  602     if (write_hashchains(c))
  603         goto recover;
  604 
  605     /* force dirty buffers to disk */
  606     fsync(c->wf.fd);
  607 
  608     /* replace old db file */
  609     strcpy(newname, c->file);
  610     strcat(newname, ".tmp");
  611     if (rename(newname, c->file) == -1) {
  612         fprintf(stderr, "RWCDB rwcdb_sync: rename failed\n");
  613         goto recover;
  614     }
  615 
  616     db_file_close(&c->wf);
  617     checkdb(c);
  618 
  619     return 1;
  620 
  621 recover: /* try to get back to the same state as before the failure */
  622     /* remove rewritten entries from the hashlists */
  623     for (i = 0; i < 256; i++) {
  624         for (p = c->added[i].next; p != &c->added[i];) {
  625             w = list_entry(p, struct wrentry, list);
  626             p = p->next;
  627             if (!w->klen && !w->dlen) {
  628                 free_wrentry(w);
  629                 c->hlens[i]--;
  630             }
  631         }
  632     }
  633     for (p = rewrites.next; p != &rewrites;) {
  634         w = list_entry(p, struct wrentry, list);
  635         p = p->next;
  636         free_wrentry(w);
  637     }
  638     return -1;
  639 }
  640