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