bfile/cfile.c

   1 /* $Id: cfile.c,v 1.33 2005-01-15 19:38:17 adam Exp $
   2    Copyright (C) 1995-2005
   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 #include <assert.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include <zebrautl.h>
  28 #include "mfile.h"
  29 #include "cfile.h"
  30
  31 static int write_head (CFile cf)
  32 {
  33     int left = cf->head.hash_size * sizeof(zint);
  34     int bno = 1;
  35     const char *tab = (char*) cf->array;
  36
  37     if (!tab)
  38         return 0;
  39     while (left >= (int) HASH_BSIZE)
  40     {
  41         mf_write (cf->hash_mf, bno++, 0, 0, tab);
  42         tab += HASH_BSIZE;
  43         left -= HASH_BSIZE;
  44     }
  45     if (left > 0)
  46         mf_write (cf->hash_mf, bno, 0, left, tab);
  47     return 0;
  48 }
  49
  50 static int read_head (CFile cf)
  51 {
  52     int left = cf->head.hash_size * sizeof(zint);
  53     int bno = 1;
  54     char *tab = (char*) cf->array;
  55
  56     if (!tab)
  57         return 0;
  58     while (left >= (int) HASH_BSIZE)
  59     {
  60         mf_read (cf->hash_mf, bno++, 0, 0, tab);
  61         tab += HASH_BSIZE;
  62         left -= HASH_BSIZE;
  63     }
  64     if (left > 0)
  65         mf_read (cf->hash_mf, bno, 0, left, tab);
  66     return 0;
  67 }
  68
  69
  70 CFile cf_open (MFile mf, MFile_area area, const char *fname,
  71                int block_size, int wflag, int *firstp)
  72 {
  73     char path[1024];
  74     int i;
  75     CFile cf = (CFile) xmalloc (sizeof(*cf));
  76     int hash_bytes;
  77
  78     cf->rmf = mf;
  79     yaz_log (YLOG_DEBUG, "cf: open %s %s", cf->rmf->name, wflag ? "rdwr" : "rd");
  80     sprintf (path, "%s-b", fname);
  81     if (!(cf->block_mf = mf_open (area, path, block_size, wflag)))
  82     {
  83         yaz_log (YLOG_FATAL|YLOG_ERRNO, "Failed to open %s", path);
  84         exit (1);
  85     }
  86     sprintf (path, "%s-i", fname);
  87     if (!(cf->hash_mf = mf_open (area, path, HASH_BSIZE, wflag)))
  88     {
  89         yaz_log (YLOG_FATAL|YLOG_ERRNO, "Failed to open %s", path);
  90         exit (1);
  91     }
  92     assert (firstp);
  93     if (!mf_read (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head) ||
  94         !cf->head.state)
  95     {
  96         *firstp = 1;
  97         cf->head.state = 1;
  98         cf->head.block_size = block_size;
  99         cf->head.hash_size = 199;
 100         hash_bytes = cf->head.hash_size * sizeof(zint);
 101         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket =
 102             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
 103         cf->head.next_block = 1;
 104         if (wflag)
 105             mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 106         cf->array = (zint *) xmalloc (hash_bytes);
 107         for (i = 0; i<cf->head.hash_size; i++)
 108             cf->array[i] = 0;
 109         if (wflag)
 110             write_head (cf);
 111     }
 112     else
 113     {
 114         *firstp = 0;
 115         assert (cf->head.block_size == block_size);
 116         assert (cf->head.hash_size > 2);
 117         hash_bytes = cf->head.hash_size * sizeof(zint);
 118         assert (cf->head.next_bucket > 0);
 119         assert (cf->head.next_block > 0);
 120         if (cf->head.state == 1)
 121             cf->array = (zint *) xmalloc (hash_bytes);
 122         else
 123             cf->array = NULL;
 124         read_head (cf);
 125     }
 126     if (cf->head.state == 1)
 127     {
 128         cf->parray = (struct CFile_hash_bucket **)
 129             xmalloc (cf->head.hash_size * sizeof(*cf->parray));
 130         for (i = 0; i<cf->head.hash_size; i++)
 131             cf->parray[i] = NULL;
 132     }
 133     else
 134         cf->parray = NULL;
 135     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
 136     cf->bucket_in_memory = 0;
 137     cf->max_bucket_in_memory = 100;
 138     cf->dirty = 0;
 139     cf->iobuf = (char *) xmalloc (cf->head.block_size);
 140     memset (cf->iobuf, 0, cf->head.block_size);
 141     cf->no_hits = 0;
 142     cf->no_miss = 0;
 143     zebra_mutex_init (&cf->mutex);
 144     return cf;
 145 }
 146
 147 static int cf_hash (CFile cf, zint no)
 148 {
 149     return (int) (((no >> 3) % cf->head.hash_size));
 150 }
 151
 152 static void release_bucket (CFile cf, struct CFile_hash_bucket *p)
 153 {
 154     if (p->lru_prev)
 155         p->lru_prev->lru_next = p->lru_next;
 156     else
 157         cf->bucket_lru_back = p->lru_next;
 158     if (p->lru_next)
 159         p->lru_next->lru_prev = p->lru_prev;
 160     else
 161         cf->bucket_lru_front = p->lru_prev;
 162
 163     *p->h_prev = p->h_next;
 164     if (p->h_next)
 165         p->h_next->h_prev = p->h_prev;
 166
 167     --(cf->bucket_in_memory);
 168     xfree (p);
 169 }
 170
 171 static void flush_bucket (CFile cf, int no_to_flush)
 172 {
 173     int i;
 174     struct CFile_hash_bucket *p;
 175
 176     for (i = 0; i != no_to_flush; i++)
 177     {
 178         p = cf->bucket_lru_back;
 179         if (!p)
 180             break;
 181         if (p->dirty)
 182         {
 183             mf_write (cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph);
 184             cf->dirty = 1;
 185         }
 186         release_bucket (cf, p);
 187     }
 188 }
 189
 190 static struct CFile_hash_bucket *alloc_bucket (CFile cf, zint block_no, int hno)
 191 {
 192     struct CFile_hash_bucket *p, **pp;
 193
 194     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
 195         flush_bucket (cf, 1);
 196     assert (cf->bucket_in_memory < cf->max_bucket_in_memory);
 197     ++(cf->bucket_in_memory);
 198     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
 199
 200     p->lru_next = NULL;
 201     p->lru_prev = cf->bucket_lru_front;
 202     if (cf->bucket_lru_front)
 203         cf->bucket_lru_front->lru_next = p;
 204     else
 205         cf->bucket_lru_back = p;
 206     cf->bucket_lru_front = p;
 207
 208     pp = cf->parray + hno;
 209     p->h_next = *pp;
 210     p->h_prev = pp;
 211     if (*pp)
 212         (*pp)->h_prev = &p->h_next;
 213     *pp = p;
 214     return p;
 215 }
 216
 217 static struct CFile_hash_bucket *get_bucket (CFile cf, zint block_no, int hno)
 218 {
 219     struct CFile_hash_bucket *p;
 220
 221     p = alloc_bucket (cf, block_no, hno);
 222     if (!mf_read (cf->hash_mf, block_no, 0, 0, &p->ph))
 223     {
 224         yaz_log (YLOG_FATAL|YLOG_ERRNO, "read get_bucket");
 225         exit (1);
 226     }
 227     assert (p->ph.this_bucket == block_no);
 228     p->dirty = 0;
 229     return p;
 230 }
 231
 232 static struct CFile_hash_bucket *new_bucket (CFile cf, zint *block_nop, int hno)
 233 {
 234     struct CFile_hash_bucket *p;
 235     int i;
 236     zint block_no;
 237
 238     block_no = *block_nop = cf->head.next_bucket++;
 239     p = alloc_bucket (cf, block_no, hno);
 240
 241     for (i = 0; i<HASH_BUCKET; i++)
 242     {
 243         p->ph.vno[i] = 0;
 244         p->ph.no[i] = 0;
 245     }
 246     p->ph.next_bucket = 0;
 247     p->ph.this_bucket = block_no;
 248     p->dirty = 1;
 249     return p;
 250 }
 251
 252 static zint cf_lookup_flat (CFile cf, zint no)
 253 {
 254     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 255     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 256     zint vno = 0;
 257
 258     mf_read (cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(zint), &vno);
 259     return vno;
 260 }
 261
 262 static zint cf_lookup_hash (CFile cf, zint no)
 263 {
 264     int hno = cf_hash (cf, no);
 265     struct CFile_hash_bucket *hb;
 266     zint block_no;
 267     int 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                 yaz_log (YLOG_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                     yaz_log (YLOG_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, zint no, zint vno)
 314 {
 315     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 316     int off = (int) ((no*sizeof(zint)) - 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(zint), &vno);
 323 }
 324
 325 static void cf_moveto_flat (CFile cf)
 326 {
 327     struct CFile_hash_bucket *p;
 328     int j;
 329     zint i;
 330
 331     yaz_log (YLOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
 332     yaz_log (YLOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT " total="
 333           ZINT_FORMAT,
 334         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 335         cf->head.next_bucket - cf->head.first_bucket);
 336     assert (cf->head.state == 1);
 337     flush_bucket (cf, -1);
 338     assert (cf->bucket_in_memory == 0);
 339     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
 340     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 341     {
 342         if (!mf_read (cf->hash_mf, i, 0, 0, &p->ph))
 343         {
 344             yaz_log (YLOG_FATAL|YLOG_ERRNO, "read bucket moveto flat");
 345             exit (1);
 346         }
 347         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 348             cf_write_flat (cf, p->ph.no[j], p->ph.vno[j]);
 349     }
 350     xfree (p);
 351     xfree (cf->array);
 352     cf->array = NULL;
 353     xfree (cf->parray);
 354     cf->parray = NULL;
 355     cf->head.state = 2;
 356     cf->dirty = 1;
 357 }
 358
 359 static zint cf_lookup (CFile cf, zint no)
 360 {
 361     if (cf->head.state > 1)
 362         return cf_lookup_flat (cf, no);
 363     return cf_lookup_hash (cf, no);
 364 }
 365
 366 static zint cf_new_flat (CFile cf, zint no)
 367 {
 368     zint vno = (cf->head.next_block)++;
 369
 370     cf_write_flat (cf, no, vno);
 371     return vno;
 372 }
 373
 374 static zint cf_new_hash (CFile cf, zint no)
 375 {
 376     int hno = cf_hash (cf, no);
 377     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 378     zint *bucketpp = &cf->array[hno];
 379     int i;
 380     zint vno = (cf->head.next_block)++;
 381
 382     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 383         if (!hb->ph.vno[HASH_BUCKET-1])
 384             for (i = 0; i<HASH_BUCKET; i++)
 385                 if (!hb->ph.vno[i])
 386                 {
 387                     (cf->no_hits)++;
 388                     hb->ph.no[i] = no;
 389                     hb->ph.vno[i] = vno;
 390                     hb->dirty = 1;
 391                     return vno;
 392                 }
 393
 394     while (*bucketpp)
 395     {
 396         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 397             if (hb->ph.this_bucket == *bucketpp)
 398             {
 399                 bucketpp = &hb->ph.next_bucket;
 400                 hbprev = hb;
 401                 break;
 402             }
 403         if (hb)
 404             continue;
 405
 406 #if 0
 407         /* extra check ... */
 408         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 409         {
 410             if (hb->ph.this_bucket == *bucketpp)
 411             {
 412                 yaz_log (YLOG_FATAL, "Found hash bucket on other chain");
 413                 abort ();
 414             }
 415         }
 416 #endif
 417         (cf->no_miss)++;
 418         hb = get_bucket (cf, *bucketpp, hno);
 419         assert (hb);
 420         for (i = 0; i<HASH_BUCKET; i++)
 421             if (!hb->ph.vno[i])
 422             {
 423                 hb->ph.no[i] = no;
 424                 hb->ph.vno[i] = vno;
 425                 hb->dirty = 1;
 426                 return vno;
 427             }
 428         bucketpp = &hb->ph.next_bucket;
 429         hbprev = hb;
 430     }
 431     if (hbprev)
 432         hbprev->dirty = 1;
 433     hb = new_bucket (cf, bucketpp, hno);
 434     hb->ph.no[0] = no;
 435     hb->ph.vno[0] = vno;
 436     return vno;
 437 }
 438
 439 zint cf_new (CFile cf, zint no)
 440 {
 441     if (cf->head.state > 1)
 442         return cf_new_flat (cf, no);
 443     if (cf->no_miss*2 > cf->no_hits)
 444     {
 445         cf_moveto_flat (cf);
 446         assert (cf->head.state > 1);
 447         return cf_new_flat (cf, no);
 448     }
 449     return cf_new_hash (cf, no);
 450 }
 451
 452
 453 int cf_read (CFile cf, zint no, int offset, int nbytes, void *buf)
 454 {
 455     zint block;
 456
 457     assert (cf);
 458     zebra_mutex_lock (&cf->mutex);
 459     if (!(block = cf_lookup (cf, no)))
 460     {
 461         zebra_mutex_unlock (&cf->mutex);
 462         return -1;
 463     }
 464     zebra_mutex_unlock (&cf->mutex);
 465     if (!mf_read (cf->block_mf, block, offset, nbytes, buf))
 466     {
 467         yaz_log (YLOG_FATAL|YLOG_ERRNO, "cf_read no=" ZINT_FORMAT " block=" ZINT_FORMAT, no, block);
 468         exit (1);
 469     }
 470     return 1;
 471 }
 472
 473 int cf_write (CFile cf, zint no, int offset, int nbytes, const void *buf)
 474 {
 475     zint block;
 476
 477     assert (cf);
 478     zebra_mutex_lock (&cf->mutex);
 479     if (!(block = cf_lookup (cf, no)))
 480     {
 481         block = cf_new (cf, no);
 482         if (offset || nbytes)
 483         {
 484             mf_read (cf->rmf, no, 0, 0, cf->iobuf);
 485             memcpy (cf->iobuf + offset, buf, nbytes);
 486             buf = cf->iobuf;
 487             offset = 0;
 488             nbytes = 0;
 489         }
 490     }
 491     zebra_mutex_unlock (&cf->mutex);
 492     if (mf_write (cf->block_mf, block, offset, nbytes, buf))
 493     {
 494         yaz_log (YLOG_FATAL|YLOG_ERRNO, "cf_write no=" ZINT_FORMAT
 495               " block=" ZINT_FORMAT, no, block);
 496         exit (1);
 497     }
 498     return 0;
 499 }
 500
 501 int cf_close (CFile cf)
 502 {
 503     yaz_log (YLOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT
 504           " total=" ZINT_FORMAT,
 505           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 506           cf->head.next_bucket - cf->head.first_bucket);
 507     flush_bucket (cf, -1);
 508     if (cf->dirty)
 509     {
 510         mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 511         write_head (cf);
 512     }
 513     mf_close (cf->hash_mf);
 514     mf_close (cf->block_mf);
 515     xfree (cf->array);
 516     xfree (cf->parray);
 517     xfree (cf->iobuf);
 518     zebra_mutex_destroy (&cf->mutex);
 519     xfree (cf);
 520     return 0;
 521 }
 522