bfile/cfile.c

   1 /* $Id: cfile.c,v 1.27 2002-08-02 19:26:55 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24
  25 #include <assert.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 #include <zebrautl.h>
  30 #include <mfile.h>
  31 #include "cfile.h"
  32
  33 static int write_head (CFile cf)
  34 {
  35     int left = cf->head.hash_size * sizeof(int);
  36     int bno = 1;
  37     const char *tab = (char*) cf->array;
  38
  39     if (!tab)
  40         return 0;
  41     while (left >= (int) HASH_BSIZE)
  42     {
  43         mf_write (cf->hash_mf, bno++, 0, 0, tab);
  44         tab += HASH_BSIZE;
  45         left -= HASH_BSIZE;
  46     }
  47     if (left > 0)
  48         mf_write (cf->hash_mf, bno, 0, left, tab);
  49     return 0;
  50 }
  51
  52 static int read_head (CFile cf)
  53 {
  54     int left = cf->head.hash_size * sizeof(int);
  55     int bno = 1;
  56     char *tab = (char*) cf->array;
  57
  58     if (!tab)
  59         return 0;
  60     while (left >= (int) HASH_BSIZE)
  61     {
  62         mf_read (cf->hash_mf, bno++, 0, 0, tab);
  63         tab += HASH_BSIZE;
  64         left -= HASH_BSIZE;
  65     }
  66     if (left > 0)
  67         mf_read (cf->hash_mf, bno, 0, left, tab);
  68     return 0;
  69 }
  70
  71
  72 CFile cf_open (MFile mf, MFile_area area, const char *fname,
  73                int block_size, int wflag, int *firstp)
  74 {
  75     char path[1024];
  76     int i;
  77     CFile cf = (CFile) xmalloc (sizeof(*cf));
  78     int hash_bytes;
  79
  80     cf->rmf = mf;
  81     logf (LOG_DEBUG, "cf: open %s %s", cf->rmf->name, wflag ? "rdwr" : "rd");
  82     sprintf (path, "%s-b", fname);
  83     if (!(cf->block_mf = mf_open (area, path, block_size, wflag)))
  84     {
  85         logf (LOG_FATAL|LOG_ERRNO, "Failed to open %s", path);
  86         exit (1);
  87     }
  88     sprintf (path, "%s-i", fname);
  89     if (!(cf->hash_mf = mf_open (area, path, HASH_BSIZE, wflag)))
  90     {
  91         logf (LOG_FATAL|LOG_ERRNO, "Failed to open %s", path);
  92         exit (1);
  93     }
  94     assert (firstp);
  95     if (!mf_read (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head) ||
  96         !cf->head.state)
  97     {
  98         *firstp = 1;
  99         cf->head.state = 1;
 100         cf->head.block_size = block_size;
 101         cf->head.hash_size = 199;
 102         hash_bytes = cf->head.hash_size * sizeof(int);
 103         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket =
 104             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
 105         cf->head.next_block = 1;
 106         if (wflag)
 107             mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 108         cf->array = (int *) xmalloc (hash_bytes);
 109         for (i = 0; i<cf->head.hash_size; i++)
 110             cf->array[i] = 0;
 111         if (wflag)
 112             write_head (cf);
 113     }
 114     else
 115     {
 116         *firstp = 0;
 117         assert (cf->head.block_size == block_size);
 118         assert (cf->head.hash_size > 2);
 119         hash_bytes = cf->head.hash_size * sizeof(int);
 120         assert (cf->head.next_bucket > 0);
 121         assert (cf->head.next_block > 0);
 122         if (cf->head.state == 1)
 123             cf->array = (int *) xmalloc (hash_bytes);
 124         else
 125             cf->array = NULL;
 126         read_head (cf);
 127     }
 128     if (cf->head.state == 1)
 129     {
 130         cf->parray = (struct CFile_hash_bucket **)
 131             xmalloc (cf->head.hash_size * sizeof(*cf->parray));
 132         for (i = 0; i<cf->head.hash_size; i++)
 133             cf->parray[i] = NULL;
 134     }
 135     else
 136         cf->parray = NULL;
 137     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
 138     cf->bucket_in_memory = 0;
 139     cf->max_bucket_in_memory = 100;
 140     cf->dirty = 0;
 141     cf->iobuf = (char *) xmalloc (cf->head.block_size);
 142     memset (cf->iobuf, 0, cf->head.block_size);
 143     cf->no_hits = 0;
 144     cf->no_miss = 0;
 145     zebra_mutex_init (&cf->mutex);
 146     return cf;
 147 }
 148
 149 static int cf_hash (CFile cf, int no)
 150 {
 151     return (no>>3) % cf->head.hash_size;
 152 }
 153
 154 static void release_bucket (CFile cf, struct CFile_hash_bucket *p)
 155 {
 156     if (p->lru_prev)
 157         p->lru_prev->lru_next = p->lru_next;
 158     else
 159         cf->bucket_lru_back = p->lru_next;
 160     if (p->lru_next)
 161         p->lru_next->lru_prev = p->lru_prev;
 162     else
 163         cf->bucket_lru_front = p->lru_prev;
 164
 165     *p->h_prev = p->h_next;
 166     if (p->h_next)
 167         p->h_next->h_prev = p->h_prev;
 168
 169     --(cf->bucket_in_memory);
 170     xfree (p);
 171 }
 172
 173 static void flush_bucket (CFile cf, int no_to_flush)
 174 {
 175     int i;
 176     struct CFile_hash_bucket *p;
 177
 178     for (i = 0; i != no_to_flush; i++)
 179     {
 180         p = cf->bucket_lru_back;
 181         if (!p)
 182             break;
 183         if (p->dirty)
 184         {
 185             mf_write (cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph);
 186             cf->dirty = 1;
 187         }
 188         release_bucket (cf, p);
 189     }
 190 }
 191
 192 static struct CFile_hash_bucket *alloc_bucket (CFile cf, int block_no, int hno)
 193 {
 194     struct CFile_hash_bucket *p, **pp;
 195
 196     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
 197         flush_bucket (cf, 1);
 198     assert (cf->bucket_in_memory < cf->max_bucket_in_memory);
 199     ++(cf->bucket_in_memory);
 200     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
 201
 202     p->lru_next = NULL;
 203     p->lru_prev = cf->bucket_lru_front;
 204     if (cf->bucket_lru_front)
 205         cf->bucket_lru_front->lru_next = p;
 206     else
 207         cf->bucket_lru_back = p;
 208     cf->bucket_lru_front = p;
 209
 210     pp = cf->parray + hno;
 211     p->h_next = *pp;
 212     p->h_prev = pp;
 213     if (*pp)
 214         (*pp)->h_prev = &p->h_next;
 215     *pp = p;
 216     return p;
 217 }
 218
 219 static struct CFile_hash_bucket *get_bucket (CFile cf, int block_no, int hno)
 220 {
 221     struct CFile_hash_bucket *p;
 222
 223     p = alloc_bucket (cf, block_no, hno);
 224     if (!mf_read (cf->hash_mf, block_no, 0, 0, &p->ph))
 225     {
 226         logf (LOG_FATAL|LOG_ERRNO, "read get_bucket");
 227         exit (1);
 228     }
 229     assert (p->ph.this_bucket == block_no);
 230     p->dirty = 0;
 231     return p;
 232 }
 233
 234 static struct CFile_hash_bucket *new_bucket (CFile cf, int *block_nop, int hno)
 235 {
 236     struct CFile_hash_bucket *p;
 237     int i, block_no;
 238
 239     block_no = *block_nop = cf->head.next_bucket++;
 240     p = alloc_bucket (cf, block_no, hno);
 241
 242     for (i = 0; i<HASH_BUCKET; i++)
 243     {
 244         p->ph.vno[i] = 0;
 245         p->ph.no[i] = 0;
 246     }
 247     p->ph.next_bucket = 0;
 248     p->ph.this_bucket = block_no;
 249     p->dirty = 1;
 250     return p;
 251 }
 252
 253 static int cf_lookup_flat (CFile cf, int no)
 254 {
 255     int hno = (no*sizeof(int))/HASH_BSIZE;
 256     int off = (no*sizeof(int)) - hno*HASH_BSIZE;
 257     int vno = 0;
 258
 259     mf_read (cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(int), &vno);
 260     return vno;
 261 }
 262
 263 static int cf_lookup_hash (CFile cf, int no)
 264 {
 265     int hno = cf_hash (cf, no);
 266     struct CFile_hash_bucket *hb;
 267     int block_no, i;
 268
 269     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 270     {
 271         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 272             if (hb->ph.no[i] == no)
 273             {
 274                 (cf->no_hits)++;
 275                 return hb->ph.vno[i];
 276             }
 277     }
 278     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
 279     {
 280         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 281         {
 282             if (hb->ph.this_bucket == block_no)
 283                 break;
 284         }
 285         if (hb)
 286             continue;
 287 #if 0
 288         /* extra check ... */
 289         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 290         {
 291             if (hb->ph.this_bucket == block_no)
 292             {
 293                 logf (LOG_FATAL, "Found hash bucket on other chain (1)");
 294                 abort ();
 295             }
 296             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 297                 if (hb->ph.no[i] == no)
 298                 {
 299                     logf (LOG_FATAL, "Found hash bucket on other chain (2)");
 300                     abort ();
 301                 }
 302         }
 303 #endif
 304         (cf->no_miss)++;
 305         hb = get_bucket (cf, block_no, hno);
 306         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 307             if (hb->ph.no[i] == no)
 308                 return hb->ph.vno[i];
 309     }
 310     return 0;
 311 }
 312
 313 static void cf_write_flat (CFile cf, int no, int vno)
 314 {
 315     int hno = (no*sizeof(int))/HASH_BSIZE;
 316     int off = (no*sizeof(int)) - hno*HASH_BSIZE;
 317
 318     hno += cf->head.next_bucket;
 319     if (hno >= cf->head.flat_bucket)
 320         cf->head.flat_bucket = hno+1;
 321     cf->dirty = 1;
 322     mf_write (cf->hash_mf, hno, off, sizeof(int), &vno);
 323 }
 324
 325 static void cf_moveto_flat (CFile cf)
 326 {
 327     struct CFile_hash_bucket *p;
 328     int i, j;
 329
 330     logf (LOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
 331     logf (LOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=%d total=%d",
 332         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 333         cf->head.next_bucket - cf->head.first_bucket);
 334     assert (cf->head.state == 1);
 335     flush_bucket (cf, -1);
 336     assert (cf->bucket_in_memory == 0);
 337     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
 338     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 339     {
 340         if (!mf_read (cf->hash_mf, i, 0, 0, &p->ph))
 341         {
 342             logf (LOG_FATAL|LOG_ERRNO, "read bucket moveto flat");
 343             exit (1);
 344         }
 345         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 346             cf_write_flat (cf, p->ph.no[j], p->ph.vno[j]);
 347     }
 348     xfree (p);
 349     xfree (cf->array);
 350     cf->array = NULL;
 351     xfree (cf->parray);
 352     cf->parray = NULL;
 353     cf->head.state = 2;
 354     cf->dirty = 1;
 355 }
 356
 357 static int cf_lookup (CFile cf, int no)
 358 {
 359     if (cf->head.state > 1)
 360         return cf_lookup_flat (cf, no);
 361     return cf_lookup_hash (cf, no);
 362 }
 363
 364 static int cf_new_flat (CFile cf, int no)
 365 {
 366     int vno = (cf->head.next_block)++;
 367
 368     cf_write_flat (cf, no, vno);
 369     return vno;
 370 }
 371
 372 static int cf_new_hash (CFile cf, int no)
 373 {
 374     int hno = cf_hash (cf, no);
 375     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 376     int *bucketpp = &cf->array[hno];
 377     int i, vno = (cf->head.next_block)++;
 378
 379     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 380         if (!hb->ph.vno[HASH_BUCKET-1])
 381             for (i = 0; i<HASH_BUCKET; i++)
 382                 if (!hb->ph.vno[i])
 383                 {
 384                     (cf->no_hits)++;
 385                     hb->ph.no[i] = no;
 386                     hb->ph.vno[i] = vno;
 387                     hb->dirty = 1;
 388                     return vno;
 389                 }
 390
 391     while (*bucketpp)
 392     {
 393         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 394             if (hb->ph.this_bucket == *bucketpp)
 395             {
 396                 bucketpp = &hb->ph.next_bucket;
 397                 hbprev = hb;
 398                 break;
 399             }
 400         if (hb)
 401             continue;
 402
 403 #if 0
 404         /* extra check ... */
 405         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 406         {
 407             if (hb->ph.this_bucket == *bucketpp)
 408             {
 409                 logf (LOG_FATAL, "Found hash bucket on other chain");
 410                 abort ();
 411             }
 412         }
 413 #endif
 414         (cf->no_miss)++;
 415         hb = get_bucket (cf, *bucketpp, hno);
 416         assert (hb);
 417         for (i = 0; i<HASH_BUCKET; i++)
 418             if (!hb->ph.vno[i])
 419             {
 420                 hb->ph.no[i] = no;
 421                 hb->ph.vno[i] = vno;
 422                 hb->dirty = 1;
 423                 return vno;
 424             }
 425         bucketpp = &hb->ph.next_bucket;
 426         hbprev = hb;
 427     }
 428     if (hbprev)
 429         hbprev->dirty = 1;
 430     hb = new_bucket (cf, bucketpp, hno);
 431     hb->ph.no[0] = no;
 432     hb->ph.vno[0] = vno;
 433     return vno;
 434 }
 435
 436 int cf_new (CFile cf, int no)
 437 {
 438     if (cf->head.state > 1)
 439         return cf_new_flat (cf, no);
 440     if (cf->no_miss*2 > cf->no_hits)
 441     {
 442         cf_moveto_flat (cf);
 443         assert (cf->head.state > 1);
 444         return cf_new_flat (cf, no);
 445     }
 446     return cf_new_hash (cf, no);
 447 }
 448
 449
 450 int cf_read (CFile cf, int no, int offset, int nbytes, void *buf)
 451 {
 452     int block;
 453
 454     assert (cf);
 455     zebra_mutex_lock (&cf->mutex);
 456     if (!(block = cf_lookup (cf, no)))
 457     {
 458         zebra_mutex_unlock (&cf->mutex);
 459         return -1;
 460     }
 461     zebra_mutex_unlock (&cf->mutex);
 462     if (!mf_read (cf->block_mf, block, offset, nbytes, buf))
 463     {
 464         logf (LOG_FATAL|LOG_ERRNO, "cf_read no=%d, block=%d", no, block);
 465         exit (1);
 466     }
 467     return 1;
 468 }
 469
 470 int cf_write (CFile cf, int no, int offset, int nbytes, const void *buf)
 471 {
 472     int block;
 473
 474     assert (cf);
 475     zebra_mutex_lock (&cf->mutex);
 476     if (!(block = cf_lookup (cf, no)))
 477     {
 478         block = cf_new (cf, no);
 479         if (offset || nbytes)
 480         {
 481             mf_read (cf->rmf, no, 0, 0, cf->iobuf);
 482             memcpy (cf->iobuf + offset, buf, nbytes);
 483             buf = cf->iobuf;
 484             offset = 0;
 485             nbytes = 0;
 486         }
 487     }
 488     zebra_mutex_unlock (&cf->mutex);
 489     if (mf_write (cf->block_mf, block, offset, nbytes, buf))
 490     {
 491         logf (LOG_FATAL|LOG_ERRNO, "cf_write no=%d, block=%d", no, block);
 492         exit (1);
 493     }
 494     return 0;
 495 }
 496
 497 int cf_close (CFile cf)
 498 {
 499     logf (LOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=%d total=%d",
 500           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 501           cf->head.next_bucket - cf->head.first_bucket);
 502     flush_bucket (cf, -1);
 503     if (cf->dirty)
 504     {
 505         mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 506         write_head (cf);
 507     }
 508     mf_close (cf->hash_mf);
 509     mf_close (cf->block_mf);
 510     xfree (cf->array);
 511     xfree (cf->parray);
 512     xfree (cf->iobuf);
 513     zebra_mutex_destroy (&cf->mutex);
 514     xfree (cf);
 515     return 0;
 516 }
 517