isam/isam.c

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