bfile/cfile.c

   1 /* $Id: cfile.c,v 1.28 2004-08-04 08:35:22 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=" ZINT_FORMAT " total="
 332           ZINT_FORMAT,
 333         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 334         cf->head.next_bucket - cf->head.first_bucket);
 335     assert (cf->head.state == 1);
 336     flush_bucket (cf, -1);
 337     assert (cf->bucket_in_memory == 0);
 338     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
 339     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 340     {
 341         if (!mf_read (cf->hash_mf, i, 0, 0, &p->ph))
 342         {
 343             logf (LOG_FATAL|LOG_ERRNO, "read bucket moveto flat");
 344             exit (1);
 345         }
 346         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 347             cf_write_flat (cf, p->ph.no[j], p->ph.vno[j]);
 348     }
 349     xfree (p);
 350     xfree (cf->array);
 351     cf->array = NULL;
 352     xfree (cf->parray);
 353     cf->parray = NULL;
 354     cf->head.state = 2;
 355     cf->dirty = 1;
 356 }
 357
 358 static int cf_lookup (CFile cf, int no)
 359 {
 360     if (cf->head.state > 1)
 361         return cf_lookup_flat (cf, no);
 362     return cf_lookup_hash (cf, no);
 363 }
 364
 365 static int cf_new_flat (CFile cf, int no)
 366 {
 367     int vno = (cf->head.next_block)++;
 368
 369     cf_write_flat (cf, no, vno);
 370     return vno;
 371 }
 372
 373 static int cf_new_hash (CFile cf, int no)
 374 {
 375     int hno = cf_hash (cf, no);
 376     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 377     int *bucketpp = &cf->array[hno];
 378     int i, vno = (cf->head.next_block)++;
 379
 380     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 381         if (!hb->ph.vno[HASH_BUCKET-1])
 382             for (i = 0; i<HASH_BUCKET; i++)
 383                 if (!hb->ph.vno[i])
 384                 {
 385                     (cf->no_hits)++;
 386                     hb->ph.no[i] = no;
 387                     hb->ph.vno[i] = vno;
 388                     hb->dirty = 1;
 389                     return vno;
 390                 }
 391
 392     while (*bucketpp)
 393     {
 394         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 395             if (hb->ph.this_bucket == *bucketpp)
 396             {
 397                 bucketpp = &hb->ph.next_bucket;
 398                 hbprev = hb;
 399                 break;
 400             }
 401         if (hb)
 402             continue;
 403
 404 #if 0
 405         /* extra check ... */
 406         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 407         {
 408             if (hb->ph.this_bucket == *bucketpp)
 409             {
 410                 logf (LOG_FATAL, "Found hash bucket on other chain");
 411                 abort ();
 412             }
 413         }
 414 #endif
 415         (cf->no_miss)++;
 416         hb = get_bucket (cf, *bucketpp, hno);
 417         assert (hb);
 418         for (i = 0; i<HASH_BUCKET; i++)
 419             if (!hb->ph.vno[i])
 420             {
 421                 hb->ph.no[i] = no;
 422                 hb->ph.vno[i] = vno;
 423                 hb->dirty = 1;
 424                 return vno;
 425             }
 426         bucketpp = &hb->ph.next_bucket;
 427         hbprev = hb;
 428     }
 429     if (hbprev)
 430         hbprev->dirty = 1;
 431     hb = new_bucket (cf, bucketpp, hno);
 432     hb->ph.no[0] = no;
 433     hb->ph.vno[0] = vno;
 434     return vno;
 435 }
 436
 437 int cf_new (CFile cf, int no)
 438 {
 439     if (cf->head.state > 1)
 440         return cf_new_flat (cf, no);
 441     if (cf->no_miss*2 > cf->no_hits)
 442     {
 443         cf_moveto_flat (cf);
 444         assert (cf->head.state > 1);
 445         return cf_new_flat (cf, no);
 446     }
 447     return cf_new_hash (cf, no);
 448 }
 449
 450
 451 int cf_read (CFile cf, zint no, int offset, int nbytes, void *buf)
 452 {
 453     int block;
 454
 455     assert (cf);
 456     zebra_mutex_lock (&cf->mutex);
 457     if (!(block = cf_lookup (cf, no)))
 458     {
 459         zebra_mutex_unlock (&cf->mutex);
 460         return -1;
 461     }
 462     zebra_mutex_unlock (&cf->mutex);
 463     if (!mf_read (cf->block_mf, block, offset, nbytes, buf))
 464     {
 465         logf (LOG_FATAL|LOG_ERRNO, "cf_read no=" ZINT_FORMAT ", block=%d", no, block);
 466         exit (1);
 467     }
 468     return 1;
 469 }
 470
 471 int cf_write (CFile cf, zint no, int offset, int nbytes, const void *buf)
 472 {
 473     int block;
 474
 475     assert (cf);
 476     zebra_mutex_lock (&cf->mutex);
 477     if (!(block = cf_lookup (cf, no)))
 478     {
 479         block = cf_new (cf, no);
 480         if (offset || nbytes)
 481         {
 482             mf_read (cf->rmf, no, 0, 0, cf->iobuf);
 483             memcpy (cf->iobuf + offset, buf, nbytes);
 484             buf = cf->iobuf;
 485             offset = 0;
 486             nbytes = 0;
 487         }
 488     }
 489     zebra_mutex_unlock (&cf->mutex);
 490     if (mf_write (cf->block_mf, block, offset, nbytes, buf))
 491     {
 492         logf (LOG_FATAL|LOG_ERRNO, "cf_write no=" ZINT_FORMAT ", block=%d", no, block);
 493         exit (1);
 494     }
 495     return 0;
 496 }
 497
 498 int cf_close (CFile cf)
 499 {
 500     logf (LOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT
 501           " total=" ZINT_FORMAT,
 502           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 503           cf->head.next_bucket - cf->head.first_bucket);
 504     flush_bucket (cf, -1);
 505     if (cf->dirty)
 506     {
 507         mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 508         write_head (cf);
 509     }
 510     mf_close (cf->hash_mf);
 511     mf_close (cf->block_mf);
 512     xfree (cf->array);
 513     xfree (cf->parray);
 514     xfree (cf->iobuf);
 515     zebra_mutex_destroy (&cf->mutex);
 516     xfree (cf);
 517     return 0;
 518 }
 519