bfile/cfile.c

   1 /*
   2  * Copyright (C) 1995, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: cfile.c,v $
   7  * Revision 1.16  1996-04-19 16:23:47  adam
   8  * Serious bug fix in shadow implementation; function new_bucket might
   9  * set wrong bucket number on new bucket.
  10  *
  11  * Revision 1.15  1996/04/18  16:02:56  adam
  12  * Changed logging a bit.
  13  * Removed warning message when commiting flat shadow files.
  14  *
  15  * Revision 1.14  1996/04/12  07:01:55  adam
  16  * Yet another bug fix (next_block was initialized to 0; now set to 1).
  17  *
  18  * Revision 1.13  1996/04/09 14:48:49  adam
  19  * Bug fix: offset calculation when using flat files was completely broken.
  20  *
  21  * Revision 1.12  1996/04/09  06:47:28  adam
  22  * Function scan_areadef doesn't use sscanf (%n fails on this Linux).
  23  *
  24  * Revision 1.11  1996/03/26 15:59:05  adam
  25  * The directory of the shadow table file can be specified by the new
  26  * bf_lockDir call.
  27  *
  28  * Revision 1.10  1996/02/07  14:03:46  adam
  29  * Work on flat indexed shadow files.
  30  *
  31  * Revision 1.9  1996/02/07  10:08:43  adam
  32  * Work on flat shadow (not finished yet).
  33  *
  34  * Revision 1.8  1995/12/15  12:36:52  adam
  35  * Moved hash file information to union.
  36  * Renamed commit files.
  37  *
  38  * Revision 1.7  1995/12/15  10:35:07  adam
  39  * Changed names of commit files.
  40  *
  41  * Revision 1.6  1995/12/11  09:03:53  adam
  42  * New function: cf_unlink.
  43  * New member of commit file head: state (0) deleted, (1) hash file.
  44  *
  45  * Revision 1.5  1995/12/08  16:21:14  adam
  46  * Work on commit/update.
  47  *
  48  * Revision 1.4  1995/12/01  16:24:28  adam
  49  * Commit files use separate meta file area.
  50  *
  51  * Revision 1.3  1995/12/01  11:37:22  adam
  52  * Cached/commit files implemented as meta-files.
  53  *
  54  * Revision 1.2  1995/11/30  17:00:49  adam
  55  * Several bug fixes. Commit system runs now.
  56  *
  57  * Revision 1.1  1995/11/30  08:33:11  adam
  58  * Started work on commit facility.
  59  *
  60  */
  61
  62 #include <assert.h>
  63 #include <stdlib.h>
  64 #include <string.h>
  65
  66 #include <alexutil.h>
  67 #include <mfile.h>
  68 #include "cfile.h"
  69
  70 static int write_head (CFile cf)
  71 {
  72     int left = cf->head.hash_size * sizeof(int);
  73     int bno = 1;
  74     const char *tab = (char*) cf->array;
  75
  76     if (!tab)
  77         return 0;
  78     while (left >= HASH_BSIZE)
  79     {
  80         mf_write (cf->hash_mf, bno++, 0, 0, tab);
  81         tab += HASH_BSIZE;
  82         left -= HASH_BSIZE;
  83     }
  84     if (left > 0)
  85         mf_write (cf->hash_mf, bno, 0, left, tab);
  86     return 0;
  87 }
  88
  89 static int read_head (CFile cf)
  90 {
  91     int left = cf->head.hash_size * sizeof(int);
  92     int bno = 1;
  93     char *tab = (char*) cf->array;
  94
  95     if (!tab)
  96         return 0;
  97     while (left >= HASH_BSIZE)
  98     {
  99         mf_read (cf->hash_mf, bno++, 0, 0, tab);
 100         tab += HASH_BSIZE;
 101         left -= HASH_BSIZE;
 102     }
 103     if (left > 0)
 104         mf_read (cf->hash_mf, bno, 0, left, tab);
 105     return 0;
 106 }
 107
 108
 109 CFile cf_open (MFile mf, MFile_area area, const char *fname,
 110                int block_size, int wflag, int *firstp)
 111 {
 112     char path[1024];
 113     int i;
 114     CFile cf = xmalloc (sizeof(*cf));
 115     int hash_bytes;
 116
 117     cf->rmf = mf;
 118     logf (LOG_LOG, "cf_open %s %s", cf->rmf->name, wflag ? "rdwr" : "rd");
 119     sprintf (path, "%s-b", fname);
 120     if (!(cf->block_mf = mf_open (area, path, block_size, wflag)))
 121     {
 122         logf (LOG_FATAL|LOG_ERRNO, "Failed to open %s", path);
 123         exit (1);
 124     }
 125     sprintf (path, "%s-i", fname);
 126     if (!(cf->hash_mf = mf_open (area, path, HASH_BSIZE, wflag)))
 127     {
 128         logf (LOG_FATAL|LOG_ERRNO, "Failed to open %s", path);
 129         exit (1);
 130     }
 131     assert (firstp);
 132     if (!mf_read (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head) ||
 133         !cf->head.state)
 134     {
 135         *firstp = 1;
 136         cf->head.state = 1;
 137         cf->head.block_size = block_size;
 138         cf->head.hash_size = 199;
 139         hash_bytes = cf->head.hash_size * sizeof(int);
 140         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket =
 141             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
 142         cf->head.next_block = 1;
 143         if (wflag)
 144             mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 145         cf->array = xmalloc (hash_bytes);
 146         for (i = 0; i<cf->head.hash_size; i++)
 147             cf->array[i] = 0;
 148         if (wflag)
 149             write_head (cf);
 150     }
 151     else
 152     {
 153         *firstp = 0;
 154         assert (cf->head.block_size == block_size);
 155         assert (cf->head.hash_size > 2);
 156         hash_bytes = cf->head.hash_size * sizeof(int);
 157         assert (cf->head.next_bucket > 0);
 158         assert (cf->head.next_block > 0);
 159         if (cf->head.state == 1)
 160             cf->array = xmalloc (hash_bytes);
 161         else
 162             cf->array = NULL;
 163         read_head (cf);
 164     }
 165     if (cf->head.state == 1)
 166     {
 167         cf->parray = xmalloc (cf->head.hash_size * sizeof(*cf->parray));
 168         for (i = 0; i<cf->head.hash_size; i++)
 169             cf->parray[i] = NULL;
 170     }
 171     else
 172         cf->parray = NULL;
 173     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
 174     cf->bucket_in_memory = 0;
 175     cf->max_bucket_in_memory = 100;
 176     cf->dirty = 0;
 177     cf->iobuf = xmalloc (cf->head.block_size);
 178     memset (cf->iobuf, 0, cf->head.block_size);
 179     cf->no_hits = 0;
 180     cf->no_miss = 0;
 181     return cf;
 182 }
 183
 184 static int cf_hash (CFile cf, int no)
 185 {
 186 #if 1
 187     return (no>>3) % cf->head.hash_size;
 188 #else
 189     return (no/(HASH_BUCKET*2+2)) % cf->head.hash_size;
 190 #endif
 191 }
 192
 193 static void release_bucket (CFile cf, struct CFile_hash_bucket *p)
 194 {
 195     if (p->lru_prev)
 196         p->lru_prev->lru_next = p->lru_next;
 197     else
 198         cf->bucket_lru_back = p->lru_next;
 199     if (p->lru_next)
 200         p->lru_next->lru_prev = p->lru_prev;
 201     else
 202         cf->bucket_lru_front = p->lru_prev;
 203
 204     *p->h_prev = p->h_next;
 205     if (p->h_next)
 206         p->h_next->h_prev = p->h_prev;
 207
 208     --(cf->bucket_in_memory);
 209     xfree (p);
 210 }
 211
 212 static void flush_bucket (CFile cf, int no_to_flush)
 213 {
 214     int i;
 215     struct CFile_hash_bucket *p;
 216
 217     for (i = 0; i != no_to_flush; i++)
 218     {
 219         p = cf->bucket_lru_back;
 220         if (!p)
 221             break;
 222         if (p->dirty)
 223         {
 224             mf_write (cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph);
 225             cf->dirty = 1;
 226         }
 227         release_bucket (cf, p);
 228     }
 229 }
 230
 231 static struct CFile_hash_bucket *alloc_bucket (CFile cf, int block_no, int hno)
 232 {
 233     struct CFile_hash_bucket *p, **pp;
 234
 235     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
 236         flush_bucket (cf, 1);
 237     assert (cf->bucket_in_memory < cf->max_bucket_in_memory);
 238     ++(cf->bucket_in_memory);
 239     p = xmalloc (sizeof(*p));
 240
 241     p->lru_next = NULL;
 242     p->lru_prev = cf->bucket_lru_front;
 243     if (cf->bucket_lru_front)
 244         cf->bucket_lru_front->lru_next = p;
 245     else
 246         cf->bucket_lru_back = p;
 247     cf->bucket_lru_front = p;
 248
 249     pp = cf->parray + hno;
 250     p->h_next = *pp;
 251     p->h_prev = pp;
 252     if (*pp)
 253         (*pp)->h_prev = &p->h_next;
 254     *pp = p;
 255     return p;
 256 }
 257
 258 static struct CFile_hash_bucket *get_bucket (CFile cf, int block_no, int hno)
 259 {
 260     struct CFile_hash_bucket *p;
 261
 262     p = alloc_bucket (cf, block_no, hno);
 263     if (!mf_read (cf->hash_mf, block_no, 0, 0, &p->ph))
 264     {
 265         logf (LOG_FATAL|LOG_ERRNO, "read get_bucket");
 266         exit (1);
 267     }
 268     assert (p->ph.this_bucket == block_no);
 269     p->dirty = 0;
 270     return p;
 271 }
 272
 273 static struct CFile_hash_bucket *new_bucket (CFile cf, int *block_nop, int hno)
 274 {
 275     struct CFile_hash_bucket *p;
 276     int i, block_no;
 277
 278     block_no = *block_nop = cf->head.next_bucket++;
 279     p = alloc_bucket (cf, block_no, hno);
 280
 281     for (i = 0; i<HASH_BUCKET; i++)
 282     {
 283         p->ph.vno[i] = 0;
 284         p->ph.no[i] = 0;
 285     }
 286     p->ph.next_bucket = 0;
 287     p->ph.this_bucket = block_no;
 288     p->dirty = 1;
 289     return p;
 290 }
 291
 292 static int cf_lookup_flat (CFile cf, int no)
 293 {
 294     int hno = (no*sizeof(int))/HASH_BSIZE;
 295     int off = (no*sizeof(int)) - hno*HASH_BSIZE;
 296     int vno = 0;
 297
 298     mf_read (cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(int), &vno);
 299     return vno;
 300 }
 301
 302 static int cf_lookup_hash (CFile cf, int no)
 303 {
 304     int hno = cf_hash (cf, no);
 305     struct CFile_hash_bucket *hb;
 306     int block_no, i;
 307
 308     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 309     {
 310         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 311             if (hb->ph.no[i] == no)
 312             {
 313                 (cf->no_hits)++;
 314                 return hb->ph.vno[i];
 315             }
 316     }
 317     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
 318     {
 319         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 320         {
 321             if (hb->ph.this_bucket == block_no)
 322                 break;
 323         }
 324         if (hb)
 325             continue;
 326 #if 1
 327         /* extra check ... */
 328         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 329         {
 330             if (hb->ph.this_bucket == block_no)
 331             {
 332                 logf (LOG_FATAL, "Found hash bucket on other chain (1)");
 333                 abort ();
 334             }
 335             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 336                 if (hb->ph.no[i] == no)
 337                 {
 338                     logf (LOG_FATAL, "Found hash bucket on other chain (2)");
 339                     abort ();
 340                 }
 341         }
 342 #endif
 343         (cf->no_miss)++;
 344         hb = get_bucket (cf, block_no, hno);
 345         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 346             if (hb->ph.no[i] == no)
 347                 return hb->ph.vno[i];
 348     }
 349     return 0;
 350 }
 351
 352 static void cf_write_flat (CFile cf, int no, int vno)
 353 {
 354     int hno = (no*sizeof(int))/HASH_BSIZE;
 355     int off = (no*sizeof(int)) - hno*HASH_BSIZE;
 356
 357     hno += cf->head.next_bucket;
 358     if (hno >= cf->head.flat_bucket)
 359         cf->head.flat_bucket = hno+1;
 360     cf->dirty = 1;
 361     mf_write (cf->hash_mf, hno, off, sizeof(int), &vno);
 362 }
 363
 364 static void cf_moveto_flat (CFile cf)
 365 {
 366     struct CFile_hash_bucket *p;
 367     int i, j;
 368
 369     logf (LOG_LOG, "Moving to flat shadow: %s", cf->rmf->name);
 370     logf (LOG_LOG, "hits=%d miss=%d bucket_in_memory=%d total=%d",
 371         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 372         cf->head.next_bucket - cf->head.first_bucket);
 373     assert (cf->head.state == 1);
 374     flush_bucket (cf, -1);
 375     assert (cf->bucket_in_memory == 0);
 376     p = xmalloc (sizeof(*p));
 377     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 378     {
 379         if (!mf_read (cf->hash_mf, i, 0, 0, &p->ph))
 380         {
 381             logf (LOG_FATAL|LOG_ERRNO, "read bucket moveto flat");
 382             exit (1);
 383         }
 384         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 385             cf_write_flat (cf, p->ph.no[j], p->ph.vno[j]);
 386     }
 387     xfree (p);
 388     xfree (cf->array);
 389     cf->array = NULL;
 390     xfree (cf->parray);
 391     cf->parray = NULL;
 392     cf->head.state = 2;
 393     cf->dirty = 1;
 394 }
 395
 396 static int cf_lookup (CFile cf, int no)
 397 {
 398     if (cf->head.state > 1)
 399         return cf_lookup_flat (cf, no);
 400     return cf_lookup_hash (cf, no);
 401 }
 402
 403 static int cf_new_flat (CFile cf, int no)
 404 {
 405     int vno = (cf->head.next_block)++;
 406
 407     cf_write_flat (cf, no, vno);
 408     return vno;
 409 }
 410
 411 static int cf_new_hash (CFile cf, int no)
 412 {
 413     int hno = cf_hash (cf, no);
 414     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 415     int *bucketpp = &cf->array[hno];
 416     int i, vno = (cf->head.next_block)++;
 417
 418     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 419         if (!hb->ph.vno[HASH_BUCKET-1])
 420             for (i = 0; i<HASH_BUCKET; i++)
 421                 if (!hb->ph.vno[i])
 422                 {
 423                     (cf->no_hits)++;
 424                     hb->ph.no[i] = no;
 425                     hb->ph.vno[i] = vno;
 426                     hb->dirty = 1;
 427                     return vno;
 428                 }
 429
 430     while (*bucketpp)
 431     {
 432         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 433             if (hb->ph.this_bucket == *bucketpp)
 434             {
 435                 bucketpp = &hb->ph.next_bucket;
 436                 hbprev = hb;
 437                 break;
 438             }
 439         if (hb)
 440             continue;
 441
 442 #if 1
 443         /* extra check ... */
 444         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 445         {
 446             if (hb->ph.this_bucket == *bucketpp)
 447             {
 448                 logf (LOG_FATAL, "Found hash bucket on other chain");
 449                 abort ();
 450             }
 451         }
 452 #endif
 453         (cf->no_miss)++;
 454         hb = get_bucket (cf, *bucketpp, hno);
 455         assert (hb);
 456         for (i = 0; i<HASH_BUCKET; i++)
 457             if (!hb->ph.vno[i])
 458             {
 459                 hb->ph.no[i] = no;
 460                 hb->ph.vno[i] = vno;
 461                 hb->dirty = 1;
 462                 return vno;
 463             }
 464         bucketpp = &hb->ph.next_bucket;
 465         hbprev = hb;
 466     }
 467     if (hbprev)
 468         hbprev->dirty = 1;
 469     hb = new_bucket (cf, bucketpp, hno);
 470     hb->ph.no[0] = no;
 471     hb->ph.vno[0] = vno;
 472     return vno;
 473 }
 474
 475 int cf_new (CFile cf, int no)
 476 {
 477     if (cf->head.state > 1)
 478         return cf_new_flat (cf, no);
 479     if (cf->no_miss*2 > cf->no_hits)
 480     {
 481         cf_moveto_flat (cf);
 482         assert (cf->head.state > 1);
 483         return cf_new_flat (cf, no);
 484     }
 485     return cf_new_hash (cf, no);
 486 }
 487
 488
 489 int cf_read (CFile cf, int no, int offset, int num, void *buf)
 490 {
 491     int block;
 492
 493     assert (cf);
 494     if (!(block = cf_lookup (cf, no)))
 495         return -1;
 496     if (!mf_read (cf->block_mf, block, offset, num, buf))
 497     {
 498         logf (LOG_FATAL|LOG_ERRNO, "cf_read no=%d, block=%d", no, block);
 499         exit (1);
 500     }
 501     return 1;
 502 }
 503
 504 int cf_write (CFile cf, int no, int offset, int num, const void *buf)
 505 {
 506     int block;
 507
 508     assert (cf);
 509     if (!(block = cf_lookup (cf, no)))
 510     {
 511         block = cf_new (cf, no);
 512         if (offset || num)
 513         {
 514             mf_read (cf->rmf, no, 0, 0, cf->iobuf);
 515             memcpy (cf->iobuf + offset, buf, num);
 516             buf = cf->iobuf;
 517             offset = 0;
 518             num = 0;
 519         }
 520     }
 521     if (mf_write (cf->block_mf, block, offset, num, buf))
 522     {
 523         logf (LOG_FATAL|LOG_ERRNO, "cf_write no=%d, block=%d", no, block);
 524         exit (1);
 525     }
 526     return 0;
 527 }
 528
 529 int cf_close (CFile cf)
 530 {
 531     logf (LOG_LOG, "hits=%d miss=%d bucket_in_memory=%d total=%d",
 532           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 533           cf->head.next_bucket - cf->head.first_bucket);
 534     flush_bucket (cf, -1);
 535     if (cf->dirty)
 536     {
 537         logf (LOG_LOG, "cf_close %s, dirty", cf->rmf->name);
 538         mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 539         write_head (cf);
 540     }
 541     else
 542         logf (LOG_LOG, "cf_close %s", cf->rmf->name);
 543     mf_close (cf->hash_mf);
 544     mf_close (cf->block_mf);
 545     xfree (cf->array);
 546     xfree (cf->parray);
 547     xfree (cf->iobuf);
 548     xfree (cf);
 549     return 0;
 550 }
 551