bfile/cfile.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2011 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20 #include <assert.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #include <idzebra/util.h>
  25 #include <yaz/yaz-util.h>
  26 #include "mfile.h"
  27 #include "cfile.h"
  28
  29 /** \brief set to 1 if extra commit/shadow check is to be performed */
  30 #define EXTRA_CHECK 0
  31
  32 static int write_head(CFile cf)
  33 {
  34     int left = cf->head.hash_size * sizeof(zint);
  35     int bno = 1;
  36     int r = 0;
  37     const char *tab = (char*) cf->array;
  38
  39     if (!tab)
  40         return 0;
  41     while (left >= (int) HASH_BSIZE)
  42     {
  43         r = mf_write(cf->hash_mf, bno++, 0, 0, tab);
  44         if (r)
  45             return r;
  46         tab += HASH_BSIZE;
  47         left -= HASH_BSIZE;
  48     }
  49     if (left > 0)
  50         r = mf_write(cf->hash_mf, bno, 0, left, tab);
  51     return r;
  52 }
  53
  54 static int read_head(CFile cf)
  55 {
  56     int left = cf->head.hash_size * sizeof(zint);
  57     int bno = 1;
  58     char *tab = (char*) cf->array;
  59
  60     if (!tab)
  61         return 0;
  62     while (left >= (int) HASH_BSIZE)
  63     {
  64         if (mf_read(cf->hash_mf, bno++, 0, 0, tab) == -1)
  65             return -1;
  66         tab += HASH_BSIZE;
  67         left -= HASH_BSIZE;
  68     }
  69     if (left > 0)
  70     {
  71         if (mf_read(cf->hash_mf, bno, 0, left, tab) == -1)
  72             return -1;
  73     }
  74     return 1;
  75 }
  76
  77
  78 CFile cf_open(MFile mf, MFile_area area, const char *fname,
  79               int block_size, int wflag, int *firstp)
  80 {
  81     char path[1024];
  82     int i, ret;
  83     CFile cf = (CFile) xmalloc(sizeof(*cf));
  84     int hash_bytes;
  85
  86     /* avoid valgrind warnings, but set to something nasty */
  87     memset(cf, 'Z', sizeof(*cf));
  88
  89     yaz_log(YLOG_DEBUG, "cf: open %s %s", fname, wflag ? "rdwr" : "rd");
  90
  91     cf->block_mf = 0;
  92     cf->hash_mf = 0;
  93     cf->rmf = mf;
  94
  95     assert(firstp);
  96
  97     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
  98     cf->bucket_in_memory = 0;
  99     cf->max_bucket_in_memory = 100;
 100     cf->dirty = 0;
 101     cf->iobuf = (char *) xmalloc(block_size);
 102     memset(cf->iobuf, 0, block_size);
 103     cf->no_hits = 0;
 104     cf->no_miss = 0;
 105     cf->parray = 0;
 106     cf->array = 0;
 107     cf->block_mf = 0;
 108     cf->hash_mf = 0;
 109
 110     zebra_mutex_init(&cf->mutex);
 111
 112     sprintf(path, "%s-b", fname);
 113     if (!(cf->block_mf = mf_open(area, path, block_size, wflag)))
 114     {
 115         cf_close(cf);
 116         return 0;
 117     }
 118     sprintf(path, "%s-i", fname);
 119     if (!(cf->hash_mf = mf_open(area, path, HASH_BSIZE, wflag)))
 120     {
 121         cf_close(cf);
 122         return 0;
 123     }
 124     ret = mf_read(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 125
 126     if (ret == -1)
 127     {
 128         cf_close(cf);
 129         return 0;
 130     }
 131     if (ret == 0 || !cf->head.state)
 132     {
 133         *firstp = 1;
 134         cf->head.state = CFILE_STATE_HASH;
 135         cf->head.block_size = block_size;
 136         cf->head.hash_size = 199;
 137         hash_bytes = cf->head.hash_size * sizeof(zint);
 138         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket =
 139             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
 140         cf->head.next_block = 1;
 141         cf->array = (zint *) xmalloc(hash_bytes);
 142         for (i = 0; i<cf->head.hash_size; i++)
 143             cf->array[i] = 0;
 144         if (wflag)
 145         {
 146             if (mf_write(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head))
 147             {
 148                 cf_close(cf);
 149                 return 0;
 150             }
 151             if (write_head(cf))
 152             {
 153                 cf_close(cf);
 154                 return 0;
 155             }
 156         }
 157     }
 158     else
 159     {
 160         *firstp = 0;
 161         assert(cf->head.block_size == block_size);
 162         assert(cf->head.hash_size > 2);
 163         hash_bytes = cf->head.hash_size * sizeof(zint);
 164         assert(cf->head.next_bucket > 0);
 165         assert(cf->head.next_block > 0);
 166         if (cf->head.state == CFILE_STATE_HASH)
 167             cf->array = (zint *) xmalloc(hash_bytes);
 168         else
 169             cf->array = NULL;
 170         if (read_head(cf) == -1)
 171         {
 172             cf_close(cf);
 173             return 0;
 174         }
 175     }
 176     if (cf->head.state == CFILE_STATE_HASH)
 177     {
 178         cf->parray = (struct CFile_hash_bucket **)
 179             xmalloc(cf->head.hash_size * sizeof(*cf->parray));
 180         for (i = 0; i<cf->head.hash_size; i++)
 181             cf->parray[i] = NULL;
 182     }
 183     return cf;
 184 }
 185
 186 static int cf_hash(CFile cf, zint no)
 187 {
 188     return (int) (((no >> 3) % cf->head.hash_size));
 189 }
 190
 191 static void release_bucket(CFile cf, struct CFile_hash_bucket *p)
 192 {
 193     if (p->lru_prev)
 194         p->lru_prev->lru_next = p->lru_next;
 195     else
 196         cf->bucket_lru_back = p->lru_next;
 197     if (p->lru_next)
 198         p->lru_next->lru_prev = p->lru_prev;
 199     else
 200         cf->bucket_lru_front = p->lru_prev;
 201
 202     *p->h_prev = p->h_next;
 203     if (p->h_next)
 204         p->h_next->h_prev = p->h_prev;
 205
 206     --(cf->bucket_in_memory);
 207     xfree(p);
 208 }
 209
 210 static int flush_bucket(CFile cf, int no_to_flush)
 211 {
 212     int i;
 213     int ret = 0;
 214     struct CFile_hash_bucket *p;
 215
 216     for (i = 0; i != no_to_flush; i++)
 217     {
 218         p = cf->bucket_lru_back;
 219         if (!p)
 220             break;
 221         if (p->dirty)
 222         {
 223             if (ret == 0)
 224             {
 225                 if (mf_write(cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph))
 226                     ret = -1;
 227             }
 228             cf->dirty = 1;
 229         }
 230         release_bucket(cf, p);
 231     }
 232     return ret;
 233 }
 234
 235 static struct CFile_hash_bucket *alloc_bucket(CFile cf, zint block_no, int hno)
 236 {
 237     struct CFile_hash_bucket *p, **pp;
 238
 239     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
 240     {
 241         if (flush_bucket(cf, 1))
 242             return 0;
 243     }
 244     assert(cf->bucket_in_memory < cf->max_bucket_in_memory);
 245     ++(cf->bucket_in_memory);
 246     p = (struct CFile_hash_bucket *) xmalloc(sizeof(*p));
 247
 248     p->lru_next = NULL;
 249     p->lru_prev = cf->bucket_lru_front;
 250     if (cf->bucket_lru_front)
 251         cf->bucket_lru_front->lru_next = p;
 252     else
 253         cf->bucket_lru_back = p;
 254     cf->bucket_lru_front = p;
 255
 256     pp = cf->parray + hno;
 257     p->h_next = *pp;
 258     p->h_prev = pp;
 259     if (*pp)
 260         (*pp)->h_prev = &p->h_next;
 261     *pp = p;
 262     return p;
 263 }
 264
 265 static struct CFile_hash_bucket *get_bucket(CFile cf, zint block_no, int hno)
 266 {
 267     struct CFile_hash_bucket *p;
 268
 269     p = alloc_bucket(cf, block_no, hno);
 270     if (!p)
 271         return 0;
 272     p->dirty = 0;
 273     if (mf_read(cf->hash_mf, block_no, 0, 0, &p->ph) != 1)
 274     {
 275         yaz_log(YLOG_FATAL, "read get_bucket");
 276         release_bucket(cf, p);
 277         return 0;
 278     }
 279     assert(p->ph.this_bucket == block_no);
 280     return p;
 281 }
 282
 283 static struct CFile_hash_bucket *new_bucket(CFile cf, zint *block_nop, int hno)
 284 {
 285     struct CFile_hash_bucket *p;
 286     int i;
 287     zint block_no;
 288
 289     block_no = *block_nop = cf->head.next_bucket++;
 290     p = alloc_bucket(cf, block_no, hno);
 291     if (!p)
 292         return 0;
 293     p->dirty = 1;
 294
 295     for (i = 0; i<HASH_BUCKET; i++)
 296     {
 297         p->ph.vno[i] = 0;
 298         p->ph.no[i] = 0;
 299     }
 300     p->ph.next_bucket = 0;
 301     p->ph.this_bucket = block_no;
 302     return p;
 303 }
 304
 305 static int cf_lookup_flat(CFile cf, zint no, zint *vno)
 306 {
 307     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 308     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 309
 310     *vno = 0;
 311     if (mf_read(cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(zint), vno)
 312         == -1)
 313         return -1;
 314     if (*vno)
 315         return 1;
 316     return 0;
 317 }
 318
 319 static int cf_lookup_hash(CFile cf, zint no, zint *vno)
 320 {
 321     int hno = cf_hash(cf, no);
 322     struct CFile_hash_bucket *hb;
 323     zint block_no;
 324     int i;
 325
 326     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 327     {
 328         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 329             if (hb->ph.no[i] == no)
 330             {
 331                 (cf->no_hits)++;
 332                 *vno = hb->ph.vno[i];
 333                 return 1;
 334             }
 335     }
 336     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
 337     {
 338         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 339         {
 340             if (hb->ph.this_bucket == block_no)
 341                 break;
 342         }
 343         if (hb)
 344             continue;
 345 #if EXTRA_CHECK
 346         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 347         {
 348             if (hb->ph.this_bucket == block_no)
 349             {
 350                 yaz_log(YLOG_FATAL, "Found hash bucket on other chain(1)");
 351                 return -1;
 352             }
 353             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 354                 if (hb->ph.no[i] == no)
 355                 {
 356                     yaz_log(YLOG_FATAL, "Found hash bucket on other chain (2)");
 357                     return -1;
 358                 }
 359         }
 360 #endif
 361         (cf->no_miss)++;
 362         hb = get_bucket(cf, block_no, hno);
 363         if (!hb)
 364             return -1;
 365         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 366             if (hb->ph.no[i] == no)
 367             {
 368                 *vno = hb->ph.vno[i];
 369                 return 1;
 370             }
 371     }
 372     return 0;
 373 }
 374
 375 static int cf_write_flat(CFile cf, zint no, zint vno)
 376 {
 377     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 378     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 379
 380     hno += cf->head.next_bucket;
 381     if (hno >= cf->head.flat_bucket)
 382         cf->head.flat_bucket = hno+1;
 383     cf->dirty = 1;
 384     return mf_write(cf->hash_mf, hno, off, sizeof(zint), &vno);
 385 }
 386
 387 static int cf_moveto_flat(CFile cf)
 388 {
 389     struct CFile_hash_bucket *p;
 390     int j;
 391     zint i;
 392
 393     yaz_log(YLOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
 394     yaz_log(YLOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT " total="
 395           ZINT_FORMAT,
 396         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 397         cf->head.next_bucket - cf->head.first_bucket);
 398     assert(cf->head.state == CFILE_STATE_HASH);
 399     if (flush_bucket(cf, -1))
 400         return -1;
 401     assert(cf->bucket_in_memory == 0);
 402     p = (struct CFile_hash_bucket *) xmalloc(sizeof(*p));
 403     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 404     {
 405         if (mf_read(cf->hash_mf, i, 0, 0, &p->ph) != 1)
 406         {
 407             yaz_log(YLOG_FATAL|YLOG_ERRNO, "read bucket moveto flat");
 408             xfree(p);
 409             return -1;
 410         }
 411         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 412         {
 413             if (cf_write_flat(cf, p->ph.no[j], p->ph.vno[j]))
 414             {
 415                 xfree(p);
 416                 return -1;
 417             }
 418         }
 419     }
 420     xfree(p);
 421     xfree(cf->array);
 422     cf->array = NULL;
 423     xfree(cf->parray);
 424     cf->parray = NULL;
 425     cf->head.state = CFILE_STATE_FLAT;
 426     cf->dirty = 1;
 427     return 0;
 428 }
 429
 430 static int cf_lookup(CFile cf, zint no, zint *vno)
 431 {
 432     if (cf->head.state > 1)
 433         return cf_lookup_flat(cf, no, vno);
 434     return cf_lookup_hash(cf, no, vno);
 435 }
 436
 437 static zint cf_new_flat(CFile cf, zint no)
 438 {
 439     zint vno = (cf->head.next_block)++;
 440
 441     cf_write_flat(cf, no, vno);
 442     return vno;
 443 }
 444
 445 static zint cf_new_hash(CFile cf, zint no)
 446 {
 447     int hno = cf_hash(cf, no);
 448     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 449     zint *bucketpp = &cf->array[hno];
 450     int i;
 451     zint vno = (cf->head.next_block)++;
 452
 453     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 454         if (!hb->ph.vno[HASH_BUCKET-1])
 455             for (i = 0; i<HASH_BUCKET; i++)
 456                 if (!hb->ph.vno[i])
 457                 {
 458                     (cf->no_hits)++;
 459                     hb->ph.no[i] = no;
 460                     hb->ph.vno[i] = vno;
 461                     hb->dirty = 1;
 462                     return vno;
 463                 }
 464
 465     while (*bucketpp)
 466     {
 467         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 468             if (hb->ph.this_bucket == *bucketpp)
 469             {
 470                 bucketpp = &hb->ph.next_bucket;
 471                 hbprev = hb;
 472                 break;
 473             }
 474         if (hb)
 475             continue;
 476
 477 #if EXTRA_CHECK
 478         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 479         {
 480             if (hb->ph.this_bucket == *bucketpp)
 481             {
 482                 yaz_log(YLOG_FATAL, "Found hash bucket on other chain");
 483                 return 0;
 484             }
 485         }
 486 #endif
 487         (cf->no_miss)++;
 488         hb = get_bucket(cf, *bucketpp, hno);
 489         if (!hb)
 490             return 0;
 491         for (i = 0; i<HASH_BUCKET; i++)
 492             if (!hb->ph.vno[i])
 493             {
 494                 hb->ph.no[i] = no;
 495                 hb->ph.vno[i] = vno;
 496                 hb->dirty = 1;
 497                 return vno;
 498             }
 499         bucketpp = &hb->ph.next_bucket;
 500         hbprev = hb;
 501     }
 502     if (hbprev)
 503         hbprev->dirty = 1;
 504     hb = new_bucket(cf, bucketpp, hno);
 505     if (!hb)
 506         return 0;
 507
 508     hb->ph.no[0] = no;
 509     hb->ph.vno[0] = vno;
 510     return vno;
 511 }
 512
 513 zint cf_new(CFile cf, zint no)
 514 {
 515     if (cf->head.state > 1)
 516         return cf_new_flat(cf, no);
 517     if (cf->no_miss*2 > cf->no_hits)
 518     {
 519         if (cf_moveto_flat(cf))
 520             return -1;
 521         assert(cf->head.state > 1);
 522         return cf_new_flat(cf, no);
 523     }
 524     return cf_new_hash(cf, no);
 525 }
 526
 527
 528 /** \brief reads block from commit area
 529     \param cf commit file
 530     \param no block number
 531     \param offset offset in block
 532     \param nbytes number of bytes to read
 533     \param buf buffer for content (if read was succesful)
 534     \retval 0 block could not be fully read
 535     \retval 1 block could be read
 536     \retval -1 error
 537 */
 538 int cf_read(CFile cf, zint no, int offset, int nbytes, void *buf)
 539 {
 540     zint block;
 541     int ret;
 542
 543     assert(cf);
 544     zebra_mutex_lock(&cf->mutex);
 545     ret = cf_lookup(cf, no, &block);
 546     zebra_mutex_unlock(&cf->mutex);
 547     if (ret == -1)
 548     {
 549         /* error */
 550         yaz_log(YLOG_FATAL, "cf_lookup failed");
 551         return -1;
 552     }
 553     else if (ret == 0)
 554     {
 555         /* block could not be read */
 556         return ret;
 557     }
 558     else if (mf_read(cf->block_mf, block, offset, nbytes, buf) != 1)
 559     {
 560         yaz_log(YLOG_FATAL|YLOG_ERRNO, "mf_read no=" ZINT_FORMAT " block=" ZINT_FORMAT, no, block);
 561         return -1;
 562     }
 563     return 1;
 564 }
 565
 566 /** \brief writes block to commit area
 567     \param cf commit file
 568     \param no block number
 569     \param offset offset in block
 570     \param nbytes number of bytes to be written
 571     \param buf buffer to be written
 572     \retval 0 block written
 573     \retval -1 error
 574 */
 575 int cf_write(CFile cf, zint no, int offset, int nbytes, const void *buf)
 576 {
 577     zint block;
 578     int ret;
 579
 580     assert(cf);
 581     zebra_mutex_lock(&cf->mutex);
 582
 583     ret = cf_lookup(cf, no, &block);
 584
 585     if (ret == -1)
 586     {
 587         zebra_mutex_unlock(&cf->mutex);
 588         return ret;
 589     }
 590     if (ret == 0)
 591     {
 592         block = cf_new(cf, no);
 593         if (!block)
 594         {
 595             zebra_mutex_unlock(&cf->mutex);
 596             return -1;
 597         }
 598         if (offset || nbytes)
 599         {
 600             if (mf_read(cf->rmf, no, 0, 0, cf->iobuf) == -1)
 601                 return -1;
 602             memcpy(cf->iobuf + offset, buf, nbytes);
 603             buf = cf->iobuf;
 604             offset = 0;
 605             nbytes = 0;
 606         }
 607     }
 608     zebra_mutex_unlock(&cf->mutex);
 609     return mf_write(cf->block_mf, block, offset, nbytes, buf);
 610 }
 611
 612 int cf_close(CFile cf)
 613 {
 614     int ret = 0;
 615     yaz_log(YLOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT
 616           " total=" ZINT_FORMAT,
 617           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 618           cf->head.next_bucket - cf->head.first_bucket);
 619     if (flush_bucket(cf, -1))
 620         ret = -1;
 621     if (cf->hash_mf)
 622     {
 623         if (cf->dirty)
 624         {
 625             if (mf_write(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head))
 626                 ret = -1;
 627             if (write_head(cf))
 628                 ret = -1;
 629         }
 630         mf_close(cf->hash_mf);
 631     }
 632     if (cf->block_mf)
 633         mf_close(cf->block_mf);
 634     xfree(cf->array);
 635     xfree(cf->parray);
 636     xfree(cf->iobuf);
 637     zebra_mutex_destroy(&cf->mutex);
 638     xfree(cf);
 639     return ret;
 640 }
 641
 642 /*
 643  * Local variables:
 644  * c-basic-offset: 4
 645  * c-file-style: "Stroustrup"
 646  * indent-tabs-mode: nil
 647  * End:
 648  * vim: shiftwidth=4 tabstop=8 expandtab
 649  */
 650