isam/isam.c

   1 /* $Id: isam.c,v 1.28 2004-01-22 11:27:21 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004
   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 <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <ctype.h>
  29
  30 #include <zebrautl.h>
  31 #include <bfile.h>
  32 #include <isam.h>
  33 #include "isutil.h"
  34 #include "rootblk.h"
  35 #include "keyops.h"
  36
  37 static ispt_struct *ispt_freelist = 0;
  38
  39 static struct
  40 {
  41     int total_merge_operations;
  42     int total_items;
  43     int dub_items_removed;
  44     int new_items;
  45     int failed_deletes;
  46     int skipped_inserts;
  47     int delete_insert_noop;
  48     int delete_replace;
  49     int deletes;
  50     int remaps;
  51     int block_jumps;
  52     int tab_deletes;
  53     int new_tables;
  54 } statistics;
  55
  56 static ISPT ispt_alloc()
  57 {
  58     ISPT p;
  59
  60     if (ispt_freelist)
  61     {
  62         p = ispt_freelist;
  63         ispt_freelist = ispt_freelist->next;
  64     }
  65     else
  66         p = (ISPT) xmalloc(sizeof(ispt_struct));
  67     return p;
  68 }
  69
  70 static void ispt_free(ISPT pt)
  71 {
  72     pt->next = ispt_freelist;
  73     ispt_freelist = pt;
  74 }
  75
  76 static int splitargs(const char *s, char *bf[], int max)
  77 {
  78     int ct = 0;
  79     for (;;)
  80     {
  81         while (*s && isspace(*s))
  82             s++;
  83         bf[ct] = (char *) s;
  84         if (!*s)
  85                 return ct;
  86         ct++;
  87         if (ct > max)
  88         {
  89             logf (LOG_WARN, "Ignoring extra args to is resource");
  90             bf[ct] = '\0';
  91             return(ct - 1);
  92         }
  93         while (*s && !isspace(*s))
  94             s++;
  95     }
  96 }
  97
  98 /*
  99  * Open isam file.
 100  * Process resources.
 101  */
 102 ISAM is_open(BFiles bfs, const char *name,
 103              int (*cmp)(const void *p1, const void *p2),
 104              int writeflag, int keysize, Res res)
 105 {
 106     ISAM inew;
 107     char *nm, *pp[IS_MAX_BLOCKTYPES+1], m[2];
 108     int num, size, rs, tmp, i;
 109     const char *r;
 110     is_type_header th;
 111
 112     logf (LOG_DEBUG, "is_open(%s, %s)", name, writeflag ? "RW" : "RDONLY");
 113     if (writeflag)
 114     {
 115         statistics.total_merge_operations = 0;
 116         statistics.total_items = 0;
 117         statistics.dub_items_removed = 0;
 118         statistics.new_items = 0;
 119         statistics.failed_deletes = 0;
 120         statistics.skipped_inserts = 0;
 121         statistics.delete_insert_noop = 0;
 122         statistics.delete_replace = 0;
 123         statistics.deletes = 0;
 124         statistics.remaps = 0;
 125         statistics.new_tables = 0;
 126         statistics.block_jumps = 0;
 127         statistics.tab_deletes = 0;
 128     }
 129
 130     inew = (ISAM) xmalloc(sizeof(*inew));
 131     inew->writeflag = writeflag;
 132     for (i = 0; i < IS_MAX_BLOCKTYPES; i++)
 133         inew->types[i].index = 0;                        /* dummy */
 134
 135     /* determine number and size of blocktypes */
 136     if (!(r = res_get_def(res,
 137                           nm = strconcat(name, ".",
 138                                          "blocktypes", 0), "64 512 4K 32K")) ||
 139         !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
 140     {
 141         logf (LOG_FATAL, "Failed to locate resource %s", nm);
 142         return 0;
 143     }
 144     inew->num_types = num;
 145     for (i = 0; i < num; i++)
 146     {
 147         if ((rs = sscanf(pp[i], "%d%1[bBkKmM]", &size, m)) < 1)
 148         {
 149             logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
 150             return 0;
 151         }
 152         if (rs == 1)
 153                 *m = 'b';
 154         switch (*m)
 155         {
 156                 case 'b': case 'B':
 157                     inew->types[i].blocksize = size; break;
 158                 case 'k': case 'K':
 159                     inew->types[i].blocksize = size * 1024; break;
 160                 case 'm': case 'M':
 161                     inew->types[i].blocksize = size * 1048576; break;
 162                 default:
 163                     logf (LOG_FATAL, "Illegal size suffix: %c", *m);
 164                     return 0;
 165         }
 166         inew->types[i].dbuf = (char *) xmalloc(inew->types[i].blocksize);
 167         m[0] = 'A' + i;
 168         m[1] = '\0';
 169         if (!(inew->types[i].bf = bf_open(bfs, strconcat(name, m, 0),
 170             inew->types[i].blocksize, writeflag)))
 171         {
 172             logf (LOG_FATAL, "bf_open failed");
 173             return 0;
 174         }
 175         if ((rs = is_rb_read(&inew->types[i], &th)) > 0)
 176         {
 177             if (th.blocksize != inew->types[i].blocksize)
 178             {
 179                 logf (LOG_FATAL, "File blocksize mismatch in %s", name);
 180                 exit(1);
 181             }
 182             inew->types[i].freelist = th.freelist;
 183             inew->types[i].top = th.top;
 184         }
 185         else if (writeflag) /* write dummy superblock to determine top */
 186         {
 187             if ((rs = is_rb_write(&inew->types[i], &th)) <=0)  /* dummy */
 188             {
 189                 logf (LOG_FATAL, "Failed to write initial superblock.");
 190                 exit(1);
 191             }
 192             inew->types[i].freelist = -1;
 193             inew->types[i].top = rs;
 194         }
 195         /* ELSE: this is an empty file opened in read-only mode. */
 196     }
 197     if (keysize > 0)
 198         inew->keysize = keysize;
 199     else
 200     {
 201         if (!(r = res_get_def(res, nm = strconcat(name, ".",
 202                                                   "keysize", 0), "4")))
 203         {
 204             logf (LOG_FATAL, "Failed to locate resource %s", nm);
 205             return 0;
 206         }
 207         if ((inew->keysize = atoi(r)) <= 0)
 208         {
 209             logf (LOG_FATAL, "Must specify positive keysize.");
 210             return 0;
 211         }
 212     }
 213
 214     /* determine repack percent */
 215     if (!(r = res_get_def(res, nm = strconcat(name, ".", "repack",
 216                                               0), IS_DEF_REPACK_PERCENT)))
 217     {
 218         logf (LOG_FATAL, "Failed to locate resource %s", nm);
 219         return 0;
 220     }
 221     inew->repack = atoi(r);
 222
 223     /* determine max keys/blocksize */
 224     if (!(r = res_get_def(res,
 225                           nm = strconcat(name, ".",
 226                                          "maxkeys", 0), "50 640 10000")) ||
 227         !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
 228     {
 229         logf (LOG_FATAL, "Failed to locate resource %s", nm);
 230         return 0;
 231     }
 232     if (num < inew->num_types -1)
 233     {
 234         logf (LOG_FATAL, "Not enough elements in %s", nm);
 235         return 0;
 236     }
 237     for (i = 0; i < num; i++)
 238     {
 239         if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
 240         {
 241             logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
 242             return 0;
 243         }
 244         inew->types[i].max_keys = tmp;
 245     }
 246
 247     /* determine max keys/block */
 248     for (i = 0; i < inew->num_types; i++)
 249     {
 250         if (!inew->types[i].index)
 251         {
 252             inew->types[i].max_keys_block = (inew->types[i].blocksize - 2 *
 253                 sizeof(int)) / inew->keysize;
 254             inew->types[i].max_keys_block0 = (inew->types[i].blocksize - 3 *
 255                 sizeof(int)) / inew->keysize;
 256         }
 257         else
 258             inew->types[i].max_keys_block = inew->types[i].max_keys_block0 /
 259                 inew->keysize;
 260         if (inew->types[i].max_keys_block0 < 1)
 261         {
 262             logf (LOG_FATAL, "Blocksize too small in %s", name);
 263             exit(1);
 264         }
 265     }
 266
 267     /* determine nice fill rates */
 268     if (!(r = res_get_def(res,
 269                           nm = strconcat(name, ".",
 270                                          "nicefill", 0), "90 90 90 95")) ||
 271         !(num = splitargs(r, pp, IS_MAX_BLOCKTYPES)))
 272     {
 273         logf (LOG_FATAL, "Failed to locate resource %s", nm);
 274         return 0;
 275     }
 276     if (num < inew->num_types)
 277     {
 278         logf (LOG_FATAL, "Not enough elements in %s", nm);
 279         return 0;
 280     }
 281     for (i = 0; i < num; i++)
 282     {
 283         if ((rs = sscanf(pp[i], "%d", &tmp)) < 1)
 284         {
 285             logf (LOG_FATAL, "Error in resource %s: %s", r, pp[i]);
 286             return 0;
 287         }
 288         inew->types[i].nice_keys_block = (inew->types[i].max_keys_block0 * tmp) /
 289             100;
 290         if (inew->types[i].nice_keys_block < 1)
 291                 inew->types[i].nice_keys_block = 1;
 292     }
 293
 294     inew->cmp = cmp ? cmp : is_default_cmp;
 295     return inew;
 296 }
 297
 298 /*
 299  * Close isam file.
 300  */
 301 int is_close(ISAM is)
 302 {
 303     int i;
 304     is_type_header th;
 305
 306     logf (LOG_DEBUG, "is_close()");
 307     for (i = 0; i < is->num_types; i++)
 308     {
 309         if (is->types[i].bf)
 310         {
 311             if (is->writeflag)
 312             {
 313                 th.blocksize = is->types[i].blocksize;
 314                 th.keysize = is->keysize;
 315                 th.freelist = is->types[i].freelist;
 316                 th.top = is->types[i].top;
 317                 if (is_rb_write(&is->types[i], &th) < 0)
 318                 {
 319                     logf (LOG_FATAL, "Failed to write headerblock");
 320                     exit(1);
 321                 }
 322             }
 323             bf_close(is->types[i].bf);
 324         }
 325     }
 326     for (i = 0; i < is->num_types; i++)
 327         xfree (is->types[i].dbuf);
 328
 329     if (is->writeflag)
 330     {
 331         logf(LOG_LOG, "ISAM statistics:");
 332         logf(LOG_LOG, "total_merge_operations      %d",
 333             statistics.total_merge_operations);
 334         logf(LOG_LOG, "total_items                 %d", statistics.total_items);
 335         logf(LOG_LOG, "dub_items_removed           %d",
 336             statistics.dub_items_removed);
 337         logf(LOG_LOG, "new_items                   %d", statistics.new_items);
 338         logf(LOG_LOG, "failed_deletes              %d",
 339             statistics.failed_deletes);
 340         logf(LOG_LOG, "skipped_inserts             %d",
 341             statistics.skipped_inserts);
 342         logf(LOG_LOG, "delete_insert_noop          %d",
 343             statistics.delete_insert_noop);
 344         logf(LOG_LOG, "delete_replace              %d",
 345             statistics.delete_replace);
 346         logf(LOG_LOG, "delete                      %d", statistics.deletes);
 347         logf(LOG_LOG, "remaps                      %d", statistics.remaps);
 348         logf(LOG_LOG, "block_jumps                 %d", statistics.block_jumps);
 349         logf(LOG_LOG, "tab_deletes                 %d", statistics.tab_deletes);
 350     }
 351     xfree(is);
 352     return 0;
 353 }
 354
 355 static ISAM_P is_address(int type, int pos)
 356 {
 357     ISAM_P r;
 358
 359     r = pos << 2;
 360     r |= type;
 361     return r;
 362 }
 363
 364 ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data)
 365 {
 366     is_mtable tab;
 367     int res;
 368     char keybuf[IS_MAX_RECORD];
 369     int oldnum, oldtype, i;
 370     char operation, *record;
 371
 372     statistics.total_merge_operations++;
 373     statistics.total_items += num;
 374     if (!pos)
 375         statistics.new_tables++;
 376
 377     is_m_establish_tab(is, &tab, pos);
 378     if (pos)
 379         if (is_m_read_full(&tab, tab.data) < 0)
 380         {
 381             logf (LOG_FATAL, "read_full failed");
 382             exit(1);
 383         }
 384     oldnum = tab.num_records;
 385     oldtype = tab.pos_type;
 386     while (num)
 387     {
 388         operation = *(data)++;
 389         record = (char*) data;
 390         data += is_keysize(is);
 391         num--;
 392         while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1))
 393         {
 394             data += 1 + is_keysize(is);
 395             num--;
 396             statistics.dub_items_removed++;
 397         }
 398         if ((res = is_m_seek_record(&tab, record)) > 0)  /* no match */
 399         {
 400             if (operation == KEYOP_INSERT)
 401             {
 402                 logf (LOG_DEBUG, "XXInserting new record.");
 403                 is_m_write_record(&tab, record);
 404                 statistics.new_items++;
 405             }
 406             else
 407             {
 408                 logf (LOG_DEBUG, "XXDeletion failed to find match.");
 409                 statistics.failed_deletes++;
 410             }
 411         }
 412         else /* match found */
 413         {
 414             if (operation == KEYOP_INSERT)
 415             {
 416                 logf (LOG_DEBUG, "XXSkipping insertion - match found.");
 417                 statistics.skipped_inserts++;
 418                 continue;
 419             }
 420             else if (operation == KEYOP_DELETE)
 421             {
 422                 /* try to avoid needlessly moving data */
 423                 if (num && *(data) == KEYOP_INSERT)
 424                 {
 425                     /* next key is identical insert? - NOOP - skip it */
 426                     if (!memcmp(record, data + 1, is_keysize(is)))
 427                     {
 428                         logf (LOG_DEBUG, "XXNoop delete. skipping.");
 429                         data += 1 + is_keysize(is);
 430                         num--;
 431                         while (num && !memcmp(data, data + is_keysize(tab.is) +
 432                             1, is_keysize(tab.is) + 1))
 433                         {
 434                             data += 1 + is_keysize(is);
 435                             num--;
 436                             statistics.dub_items_removed++;
 437                         }
 438                         statistics.delete_insert_noop++;
 439                         continue;
 440                     }
 441                     /* else check if next key can fit in this position */
 442                     if (is_m_peek_record(&tab, keybuf) &&
 443                         (*is->cmp)(data + 1, keybuf) < 0)
 444                     {
 445                         logf (LOG_DEBUG, "XXReplacing record.");
 446                         is_m_replace_record(&tab, data + 1);
 447                         data += 1 + is_keysize(is);
 448                         num--;
 449                         while (num && !memcmp(data, data + is_keysize(tab.is) +
 450                             1, is_keysize(tab.is) + 1))
 451                         {
 452                             data += 1 + is_keysize(is);
 453                             num--;
 454                             statistics.dub_items_removed++;
 455                         }
 456                         statistics.delete_replace++;
 457                         continue;
 458                     }
 459                 }
 460                 logf (LOG_DEBUG, "Deleting record.");
 461                 is_m_delete_record(&tab);
 462                 statistics.deletes++;
 463             }
 464         }
 465     }
 466     i = tab.pos_type;
 467     while (i < tab.is->num_types - 1 && tab.num_records >
 468         tab.is->types[i].max_keys)
 469         i++;
 470     if (i != tab.pos_type)
 471     {
 472         /* read remaining blocks */
 473         for (; tab.cur_mblock; tab.cur_mblock = tab.cur_mblock->next)
 474             if (tab.cur_mblock->state < IS_MBSTATE_CLEAN)
 475                 is_m_read_full(&tab, tab.cur_mblock);
 476         is_p_unmap(&tab);
 477         tab.pos_type = i;
 478         if (pos)
 479             statistics.block_jumps++;
 480     }
 481     if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) *
 482         100) / oldnum > tab.is->repack)
 483     {
 484         is_p_remap(&tab);
 485         statistics.remaps++;
 486     }
 487     else
 488         is_p_align(&tab);
 489     if (tab.data)
 490     {
 491         is_p_sync(&tab);
 492         pos = is_address(tab.pos_type, tab.data->diskpos);
 493     }
 494     else
 495     {
 496         pos = 0;
 497         statistics.tab_deletes++;
 498     }
 499     is_m_release_tab(&tab);
 500     return pos;
 501 }
 502
 503 /*
 504  * Locate a table of keys in an isam file. The ISPT is an individual
 505  * position marker for that table.
 506  */
 507 ISPT is_position(ISAM is, ISAM_P pos)
 508 {
 509     ispt_struct *p;
 510
 511     p = ispt_alloc();
 512     is_m_establish_tab(is, &p->tab, pos);
 513     return p;
 514 }
 515
 516 /*
 517  * Release ISPT.
 518  */
 519 void is_pt_free(ISPT ip)
 520 {
 521     is_m_release_tab(&ip->tab);
 522     ispt_free(ip);
 523 }
 524
 525 /*
 526  * Read a key from a table.
 527  */
 528 int is_readkey(ISPT ip, void *buf)
 529 {
 530     return is_m_read_record(&ip->tab, buf, 0);
 531 }
 532
 533 int is_numkeys(ISPT ip)
 534 {
 535     return is_m_num_records(&ip->tab);
 536 }
 537
 538 void is_rewind(ISPT ip)
 539 {
 540     is_m_rewind(&ip->tab);
 541 }