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