bfile/cfile.c

   1 /* $Id: cfile.c,v 1.29 2004-08-06 12:28: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(zint);
  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(zint);
  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(zint);
 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 = (zint *) 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(zint);
 120         assert (cf->head.next_bucket > 0);
 121         assert (cf->head.next_block > 0);
 122         if (cf->head.state == 1)
 123             cf->array = (zint *) 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, zint no)
 150 {
 151     return (int) (((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, zint 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, zint 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, zint *block_nop, int hno)
 235 {
 236     struct CFile_hash_bucket *p;
 237     int i;
 238     zint block_no;
 239
 240     block_no = *block_nop = cf->head.next_bucket++;
 241     p = alloc_bucket (cf, block_no, hno);
 242
 243     for (i = 0; i<HASH_BUCKET; i++)
 244     {
 245         p->ph.vno[i] = 0;
 246         p->ph.no[i] = 0;
 247     }
 248     p->ph.next_bucket = 0;
 249     p->ph.this_bucket = block_no;
 250     p->dirty = 1;
 251     return p;
 252 }
 253
 254 static zint cf_lookup_flat (CFile cf, zint no)
 255 {
 256     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 257     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 258     zint vno = 0;
 259
 260     mf_read (cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(zint), &vno);
 261     return vno;
 262 }
 263
 264 static zint cf_lookup_hash (CFile cf, zint no)
 265 {
 266     int hno = cf_hash (cf, no);
 267     struct CFile_hash_bucket *hb;
 268     zint block_no;
 269     int i;
 270
 271     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 272     {
 273         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 274             if (hb->ph.no[i] == no)
 275             {
 276                 (cf->no_hits)++;
 277                 return hb->ph.vno[i];
 278             }
 279     }
 280     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
 281     {
 282         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 283         {
 284             if (hb->ph.this_bucket == block_no)
 285                 break;
 286         }
 287         if (hb)
 288             continue;
 289 #if 0
 290         /* extra check ... */
 291         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 292         {
 293             if (hb->ph.this_bucket == block_no)
 294             {
 295                 logf (LOG_FATAL, "Found hash bucket on other chain (1)");
 296                 abort ();
 297             }
 298             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 299                 if (hb->ph.no[i] == no)
 300                 {
 301                     logf (LOG_FATAL, "Found hash bucket on other chain (2)");
 302                     abort ();
 303                 }
 304         }
 305 #endif
 306         (cf->no_miss)++;
 307         hb = get_bucket (cf, block_no, hno);
 308         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 309             if (hb->ph.no[i] == no)
 310                 return hb->ph.vno[i];
 311     }
 312     return 0;
 313 }
 314
 315 static void cf_write_flat (CFile cf, zint no, zint vno)
 316 {
 317     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 318     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 319
 320     hno += cf->head.next_bucket;
 321     if (hno >= cf->head.flat_bucket)
 322         cf->head.flat_bucket = hno+1;
 323     cf->dirty = 1;
 324     mf_write (cf->hash_mf, hno, off, sizeof(zint), &vno);
 325 }
 326
 327 static void cf_moveto_flat (CFile cf)
 328 {
 329     struct CFile_hash_bucket *p;
 330     int j;
 331     zint i;
 332
 333     logf (LOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
 334     logf (LOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT " total="
 335           ZINT_FORMAT,
 336         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 337         cf->head.next_bucket - cf->head.first_bucket);
 338     assert (cf->head.state == 1);
 339     flush_bucket (cf, -1);
 340     assert (cf->bucket_in_memory == 0);
 341     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
 342     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 343     {
 344         if (!mf_read (cf->hash_mf, i, 0, 0, &p->ph))
 345         {
 346             logf (LOG_FATAL|LOG_ERRNO, "read bucket moveto flat");
 347             exit (1);
 348         }
 349         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 350             cf_write_flat (cf, p->ph.no[j], p->ph.vno[j]);
 351     }
 352     xfree (p);
 353     xfree (cf->array);
 354     cf->array = NULL;
 355     xfree (cf->parray);
 356     cf->parray = NULL;
 357     cf->head.state = 2;
 358     cf->dirty = 1;
 359 }
 360
 361 static zint cf_lookup (CFile cf, zint 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 zint cf_new_flat (CFile cf, zint no)
 369 {
 370     zint vno = (cf->head.next_block)++;
 371
 372     cf_write_flat (cf, no, vno);
 373     return vno;
 374 }
 375
 376 static zint cf_new_hash (CFile cf, zint no)
 377 {
 378     int hno = cf_hash (cf, no);
 379     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 380     zint *bucketpp = &cf->array[hno];
 381     int i;
 382     zint vno = (cf->head.next_block)++;
 383
 384     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 385         if (!hb->ph.vno[HASH_BUCKET-1])
 386             for (i = 0; i<HASH_BUCKET; i++)
 387                 if (!hb->ph.vno[i])
 388                 {
 389                     (cf->no_hits)++;
 390                     hb->ph.no[i] = no;
 391                     hb->ph.vno[i] = vno;
 392                     hb->dirty = 1;
 393                     return vno;
 394                 }
 395
 396     while (*bucketpp)
 397     {
 398         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 399             if (hb->ph.this_bucket == *bucketpp)
 400             {
 401                 bucketpp = &hb->ph.next_bucket;
 402                 hbprev = hb;
 403                 break;
 404             }
 405         if (hb)
 406             continue;
 407
 408 #if 0
 409         /* extra check ... */
 410         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 411         {
 412             if (hb->ph.this_bucket == *bucketpp)
 413             {
 414                 logf (LOG_FATAL, "Found hash bucket on other chain");
 415                 abort ();
 416             }
 417         }
 418 #endif
 419         (cf->no_miss)++;
 420         hb = get_bucket (cf, *bucketpp, hno);
 421         assert (hb);
 422         for (i = 0; i<HASH_BUCKET; i++)
 423             if (!hb->ph.vno[i])
 424             {
 425                 hb->ph.no[i] = no;
 426                 hb->ph.vno[i] = vno;
 427                 hb->dirty = 1;
 428                 return vno;
 429             }
 430         bucketpp = &hb->ph.next_bucket;
 431         hbprev = hb;
 432     }
 433     if (hbprev)
 434         hbprev->dirty = 1;
 435     hb = new_bucket (cf, bucketpp, hno);
 436     hb->ph.no[0] = no;
 437     hb->ph.vno[0] = vno;
 438     return vno;
 439 }
 440
 441 zint cf_new (CFile cf, zint no)
 442 {
 443     if (cf->head.state > 1)
 444         return cf_new_flat (cf, no);
 445     if (cf->no_miss*2 > cf->no_hits)
 446     {
 447         cf_moveto_flat (cf);
 448         assert (cf->head.state > 1);
 449         return cf_new_flat (cf, no);
 450     }
 451     return cf_new_hash (cf, no);
 452 }
 453
 454
 455 int cf_read (CFile cf, zint no, int offset, int nbytes, void *buf)
 456 {
 457     zint block;
 458
 459     assert (cf);
 460     zebra_mutex_lock (&cf->mutex);
 461     if (!(block = cf_lookup (cf, no)))
 462     {
 463         zebra_mutex_unlock (&cf->mutex);
 464         return -1;
 465     }
 466     zebra_mutex_unlock (&cf->mutex);
 467     if (!mf_read (cf->block_mf, block, offset, nbytes, buf))
 468     {
 469         logf (LOG_FATAL|LOG_ERRNO, "cf_read no=" ZINT_FORMAT ", block=%d", no, block);
 470         exit (1);
 471     }
 472     return 1;
 473 }
 474
 475 int cf_write (CFile cf, zint no, int offset, int nbytes, const void *buf)
 476 {
 477     zint block;
 478
 479     assert (cf);
 480     zebra_mutex_lock (&cf->mutex);
 481     if (!(block = cf_lookup (cf, no)))
 482     {
 483         block = cf_new (cf, no);
 484         if (offset || nbytes)
 485         {
 486             mf_read (cf->rmf, no, 0, 0, cf->iobuf);
 487             memcpy (cf->iobuf + offset, buf, nbytes);
 488             buf = cf->iobuf;
 489             offset = 0;
 490             nbytes = 0;
 491         }
 492     }
 493     zebra_mutex_unlock (&cf->mutex);
 494     if (mf_write (cf->block_mf, block, offset, nbytes, buf))
 495     {
 496         logf (LOG_FATAL|LOG_ERRNO, "cf_write no=" ZINT_FORMAT ", block=%d", no, block);
 497         exit (1);
 498     }
 499     return 0;
 500 }
 501
 502 int cf_close (CFile cf)
 503 {
 504     logf (LOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT
 505           " total=" ZINT_FORMAT,
 506           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 507           cf->head.next_bucket - cf->head.first_bucket);
 508     flush_bucket (cf, -1);
 509     if (cf->dirty)
 510     {
 511         mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 512         write_head (cf);
 513     }
 514     mf_close (cf->hash_mf);
 515     mf_close (cf->block_mf);
 516     xfree (cf->array);
 517     xfree (cf->parray);
 518     xfree (cf->iobuf);
 519     zebra_mutex_destroy (&cf->mutex);
 520     xfree (cf);
 521     return 0;
 522 }
 523