| 1 |
/* |
| 2 |
* Copyright (c) 2011, Secure Endpoints Inc. |
| 3 |
* All rights reserved. |
| 4 |
* |
| 5 |
* Redistribution and use in source and binary forms, with or without |
| 6 |
* modification, are permitted provided that the following conditions |
| 7 |
* are met: |
| 8 |
* |
| 9 |
* - Redistributions of source code must retain the above copyright |
| 10 |
* notice, this list of conditions and the following disclaimer. |
| 11 |
* |
| 12 |
* - Redistributions in binary form must reproduce the above copyright |
| 13 |
* notice, this list of conditions and the following disclaimer in |
| 14 |
* the documentation and/or other materials provided with the |
| 15 |
* distribution. |
| 16 |
* |
| 17 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 18 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 19 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS |
| 20 |
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE |
| 21 |
* COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, |
| 22 |
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
| 23 |
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| 24 |
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 25 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 26 |
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 27 |
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 28 |
* OF THE POSSIBILITY OF SUCH DAMAGE. |
| 29 |
* |
| 30 |
*/ |
| 31 |
|
| 32 |
#include "baselocl.h" |
| 33 |
|
| 34 |
#include <sys/types.h> |
| 35 |
#include <sys/stat.h> |
| 36 |
#ifdef HAVE_IO_H |
| 37 |
#include <io.h> |
| 38 |
#endif |
| 39 |
#ifdef HAVE_UNISTD_H |
| 40 |
#include <unistd.h> |
| 41 |
#endif |
| 42 |
#include <fcntl.h> |
| 43 |
#include <ctype.h> |
| 44 |
#include <stdio.h> |
| 45 |
#include <stdlib.h> |
| 46 |
#include <string.h> |
| 47 |
#ifdef HAVE_STRINGS_H |
| 48 |
#include <strings.h> |
| 49 |
#endif |
| 50 |
#include <errno.h> |
| 51 |
#include <assert.h> |
| 52 |
|
| 53 |
/* |
| 54 |
* This file contains functions for binary searching flat text in memory |
| 55 |
* and in text files where each line is a [variable length] record. |
| 56 |
* Each record has a key and an optional value separated from the key by |
| 57 |
* unquoted whitespace. Whitespace in the key, and leading whitespace |
| 58 |
* for the value, can be quoted with backslashes (but CR and LF must be |
| 59 |
* quoted in such a way that they don't appear in the quoted result). |
| 60 |
* |
| 61 |
* Binary searching a tree are normally a dead simple algorithm. It |
| 62 |
* turns out that binary searching flat text with *variable* length |
| 63 |
* records is... tricky. There's no indexes to record beginning bytes, |
| 64 |
* thus any index selected during the search is likely to fall in the |
| 65 |
* middle of a record. When deciding to search a left sub-tree one |
| 66 |
* might fail to find the last record in that sub-tree on account of the |
| 67 |
* right boundary falling in the middle of it -- the chosen solution to |
| 68 |
* this makes left sub-tree searches slightly less efficient than right |
| 69 |
* sub-tree searches. |
| 70 |
* |
| 71 |
* If binary searching flat text in memory is tricky, using block-wise |
| 72 |
* I/O instead is trickier! But it's necessary in order to support |
| 73 |
* large files (which we either can't or wouldn't want to read or map |
| 74 |
* into memory). Each block we read has to be large enough that the |
| 75 |
* largest record can fit in it. And each block might start and/or end |
| 76 |
* in the middle of a record. Here it is the right sub-tree searches |
| 77 |
* that are less efficient than left sub-tree searches. |
| 78 |
* |
| 79 |
* bsearch_common() contains the common text block binary search code. |
| 80 |
* |
| 81 |
* _bsearch_text() is the interface for searching in-core text. |
| 82 |
* _bsearch_file() is the interface for block-wise searching files. |
| 83 |
*/ |
| 84 |
|
| 85 |
struct bsearch_file_handle { |
| 86 |
int fd; /* file descriptor */ |
| 87 |
char *cache; /* cache bytes */ |
| 88 |
char *page; /* one double-size page worth of bytes */ |
| 89 |
size_t file_sz; /* file size */ |
| 90 |
size_t cache_sz; /* cache size */ |
| 91 |
size_t page_sz; /* page size */ |
| 92 |
}; |
| 93 |
|
| 94 |
/* Find a new-line */ |
| 95 |
static const char * |
| 96 |
find_line(const char *buf, size_t i, size_t right) |
| 97 |
{ |
| 98 |
if (i == 0) |
| 99 |
return &buf[i]; |
| 100 |
for (; i < right; i++) { |
| 101 |
if (buf[i] == '\n') { |
| 102 |
if ((i + 1) < right) |
| 103 |
return &buf[i + 1]; |
| 104 |
return NULL; |
| 105 |
} |
| 106 |
} |
| 107 |
return NULL; |
| 108 |
} |
| 109 |
|
| 110 |
/* |
| 111 |
* Common routine for binary searching text in core. |
| 112 |
* |
| 113 |
* Perform a binary search of a char array containing a block from a |
| 114 |
* text file where each line is a record (LF and CRLF supported). Each |
| 115 |
* record consists of a key followed by an optional value separated from |
| 116 |
* the key by whitespace. Whitespace can be quoted with backslashes. |
| 117 |
* It's the caller's responsibility to encode/decode keys/values if |
| 118 |
* quoting is desired; newlines should be encoded such that a newline |
| 119 |
* does not appear in the result. |
| 120 |
* |
| 121 |
* All output arguments are optional. |
| 122 |
* |
| 123 |
* Returns 0 if key is found, -1 if not found, or an error code such as |
| 124 |
* ENOMEM in case of error. |
| 125 |
* |
| 126 |
* Inputs: |
| 127 |
* |
| 128 |
* @buf String to search |
| 129 |
* @sz Size of string to search |
| 130 |
* @key Key string to search for |
| 131 |
* @buf_is_start True if the buffer starts with a record, false if it |
| 132 |
* starts in the middle of a record or if the caller |
| 133 |
* doesn't know. |
| 134 |
* |
| 135 |
* Outputs: |
| 136 |
* |
| 137 |
* @value Location to store a copy of the value (caller must free) |
| 138 |
* @location Record location if found else the location where the |
| 139 |
* record should be inserted (index into @buf) |
| 140 |
* @cmp Set to less than or greater than 0 to indicate that a |
| 141 |
* key not found would have fit in an earlier or later |
| 142 |
* part of a file. Callers should use this to decide |
| 143 |
* whether to read a block to the left or to the right and |
| 144 |
* search that. |
| 145 |
* @loops Location to store a count of bisections required for |
| 146 |
* search (useful for confirming logarithmic performance) |
| 147 |
*/ |
| 148 |
static int |
| 149 |
bsearch_common(const char *buf, size_t sz, const char *key, |
| 150 |
int buf_is_start, char **value, size_t *location, |
| 151 |
int *cmp, size_t *loops) |
| 152 |
{ |
| 153 |
const char *linep; |
| 154 |
size_t key_start, key_len; /* key string in buf */ |
| 155 |
size_t val_start, val_len; /* value string in buf */ |
| 156 |
int key_cmp = -1; |
| 157 |
size_t k; |
| 158 |
size_t l; /* left side of buffer for binary search */ |
| 159 |
size_t r; /* right side of buffer for binary search */ |
| 160 |
size_t rmax; /* right side of buffer for binary search */ |
| 161 |
size_t i; /* index into buffer, typically in the middle of l and r */ |
| 162 |
size_t loop_count = 0; |
| 163 |
int ret = -1; |
| 164 |
|
| 165 |
if (value) |
| 166 |
*value = NULL; |
| 167 |
if (cmp) |
| 168 |
*cmp = 0; |
| 169 |
if (loops) |
| 170 |
*loops = 0; |
| 171 |
|
| 172 |
/* Binary search; file should be sorted */ |
| 173 |
for (l = 0, r = rmax = sz, i = sz >> 1; i >= l && i < rmax; loop_count++) { |
| 174 |
heim_assert(i < sz, "invalid aname2lname db index"); |
| 175 |
|
| 176 |
/* buf[i] is likely in the middle of a line; find the next line */ |
| 177 |
linep = find_line(buf, i, rmax); |
| 178 |
k = linep ? linep - buf : i; |
| 179 |
if (linep == NULL || k >= rmax) { |
| 180 |
/* |
| 181 |
* No new line found to the right; search to the left then |
| 182 |
* but don't change rmax (this isn't optimal, but it's |
| 183 |
* simple). |
| 184 |
*/ |
| 185 |
if (i == l) |
| 186 |
break; |
| 187 |
r = i; |
| 188 |
i = l + ((r - l) >> 1); |
| 189 |
continue; |
| 190 |
} |
| 191 |
i = k; |
| 192 |
heim_assert(i >= l && i < rmax, "invalid aname2lname db index"); |
| 193 |
|
| 194 |
/* Got a line; check it */ |
| 195 |
|
| 196 |
/* Search for and split on unquoted whitespace */ |
| 197 |
val_start = 0; |
| 198 |
for (key_start = i, key_len = 0, val_len = 0, k = i; k < rmax; k++) { |
| 199 |
if (buf[k] == '\\') { |
| 200 |
k++; |
| 201 |
continue; |
| 202 |
} |
| 203 |
if (buf[k] == '\r' || buf[k] == '\n') { |
| 204 |
/* We now know where the key ends, and there's no value */ |
| 205 |
key_len = k - i; |
| 206 |
break; |
| 207 |
} |
| 208 |
if (!isspace((unsigned char)buf[k])) |
| 209 |
continue; |
| 210 |
|
| 211 |
while (k < rmax && isspace((unsigned char)buf[k])) { |
| 212 |
key_len = k - i; |
| 213 |
k++; |
| 214 |
} |
| 215 |
if (k < rmax) |
| 216 |
val_start = k; |
| 217 |
/* Find end of value */ |
| 218 |
for (; k < rmax && buf[k] != '\0'; k++) { |
| 219 |
if (buf[k] == '\r' || buf[k] == '\n') { |
| 220 |
val_len = k - val_start; |
| 221 |
break; |
| 222 |
} |
| 223 |
} |
| 224 |
break; |
| 225 |
} |
| 226 |
|
| 227 |
/* |
| 228 |
* The following logic is for dealing with partial buffers, |
| 229 |
* which we use for block-wise binary searches of large files |
| 230 |
*/ |
| 231 |
if (key_start == 0 && !buf_is_start) { |
| 232 |
/* |
| 233 |
* We're at the beginning of a block that might have started |
| 234 |
* in the middle of a record whose "key" might well compare |
| 235 |
* as greater than the key we're looking for, so we don't |
| 236 |
* bother comparing -- we know key_cmp must be -1 here. |
| 237 |
*/ |
| 238 |
key_cmp = -1; |
| 239 |
break; |
| 240 |
} |
| 241 |
if ((val_len && buf[val_start + val_len] != '\n') || |
| 242 |
(!val_len && buf[key_start + key_len] != '\n')) { |
| 243 |
/* |
| 244 |
* We're at the end of a block that ends in the middle of a |
| 245 |
* record whose "key" might well compare as less than the |
| 246 |
* key we're looking for, so we don't bother comparing -- we |
| 247 |
* know key_cmp must be >= 0 but we can't tell. Our caller |
| 248 |
* will end up reading a double-size block to handle this. |
| 249 |
*/ |
| 250 |
key_cmp = 1; |
| 251 |
break; |
| 252 |
} |
| 253 |
|
| 254 |
key_cmp = strncmp(key, &buf[key_start], key_len); |
| 255 |
if (key_cmp == 0 && strlen(key) != key_len) |
| 256 |
key_cmp = 1; |
| 257 |
if (key_cmp < 0) { |
| 258 |
/* search left */ |
| 259 |
r = rmax = (linep - buf); |
| 260 |
i = l + ((r - l) >> 1); |
| 261 |
if (location) |
| 262 |
*location = key_start; |
| 263 |
} else if (key_cmp > 0) { |
| 264 |
/* search right */ |
| 265 |
if (l == i) |
| 266 |
break; /* not found */ |
| 267 |
l = i; |
| 268 |
i = l + ((r - l) >> 1); |
| 269 |
if (location) |
| 270 |
*location = val_start + val_len; |
| 271 |
} else { |
| 272 |
/* match! */ |
| 273 |
if (location) |
| 274 |
*location = key_start; |
| 275 |
ret = 0; |
| 276 |
if (val_len && value) { |
| 277 |
/* Avoid strndup() so we don't need libroken here yet */ |
| 278 |
if ((*value = malloc(val_len + 1))) { |
| 279 |
(void) memcpy(*value, &buf[val_start], val_len); |
| 280 |
(*value)[val_len] = '\0'; |
| 281 |
} else { |
| 282 |
ret = errno; |
| 283 |
} |
| 284 |
} |
| 285 |
break; |
| 286 |
} |
| 287 |
} |
| 288 |
|
| 289 |
if (cmp) |
| 290 |
*cmp = key_cmp; |
| 291 |
if (loops) |
| 292 |
*loops = loop_count; |
| 293 |
|
| 294 |
return ret; |
| 295 |
} |
| 296 |
|
| 297 |
/* |
| 298 |
* Binary search a char array containing sorted text records separated |
| 299 |
* by new-lines (or CRLF). Each record consists of a key and an |
| 300 |
* optional value following the key, separated from the key by unquoted |
| 301 |
* whitespace. |
| 302 |
* |
| 303 |
* All output arguments are optional. |
| 304 |
* |
| 305 |
* Returns 0 if key is found, -1 if not found, or an error code such as |
| 306 |
* ENOMEM in case of error. |
| 307 |
* |
| 308 |
* Inputs: |
| 309 |
* |
| 310 |
* @buf Char array pointer |
| 311 |
* @buf_sz Size of buf |
| 312 |
* @key Key to search for |
| 313 |
* |
| 314 |
* Outputs: |
| 315 |
* |
| 316 |
* @value Location where to put the value, if any (caller must free) |
| 317 |
* @location Record location if found else the location where the record |
| 318 |
* should be inserted (index into @buf) |
| 319 |
* @loops Location where to put a number of loops (or comparisons) |
| 320 |
* needed for the search (useful for benchmarking) |
| 321 |
*/ |
| 322 |
int |
| 323 |
_bsearch_text(const char *buf, size_t buf_sz, const char *key, |
| 324 |
char **value, size_t *location, size_t *loops) |
| 325 |
{ |
| 326 |
return bsearch_common(buf, buf_sz, key, 1, value, location, NULL, loops); |
| 327 |
} |
| 328 |
|
| 329 |
#define MAX_BLOCK_SIZE (1024 * 1024) |
| 330 |
#define DEFAULT_MAX_FILE_SIZE (1024 * 1024) |
| 331 |
/* |
| 332 |
* Open a file for binary searching. The file will be read in entirely |
| 333 |
* if it is smaller than @max_sz, else a cache of @max_sz bytes will be |
| 334 |
* allocated. |
| 335 |
* |
| 336 |
* Returns 0 on success, else an error number or -1 if the file is empty. |
| 337 |
* |
| 338 |
* Inputs: |
| 339 |
* |
| 340 |
* @fname Name of file to open |
| 341 |
* @max_sz Maximum size of cache to allocate, in bytes (if zero, default) |
| 342 |
* @page_sz Page size (must be a power of two, larger than 256, smaller |
| 343 |
* than 1MB; if zero use default) |
| 344 |
* |
| 345 |
* Outputs: |
| 346 |
* |
| 347 |
* @bfh Handle for use with _bsearch_file() and _bsearch_file_close() |
| 348 |
* @reads Number of reads performed |
| 349 |
*/ |
| 350 |
int |
| 351 |
_bsearch_file_open(const char *fname, size_t max_sz, size_t page_sz, |
| 352 |
bsearch_file_handle *bfh, size_t *reads) |
| 353 |
{ |
| 354 |
bsearch_file_handle new_bfh = NULL; |
| 355 |
struct stat st; |
| 356 |
size_t i; |
| 357 |
int fd; |
| 358 |
int ret; |
| 359 |
|
| 360 |
*bfh = NULL; |
| 361 |
|
| 362 |
if (reads) |
| 363 |
*reads = 0; |
| 364 |
|
| 365 |
fd = open(fname, O_RDONLY); |
| 366 |
if (fd == -1) |
| 367 |
return errno; |
| 368 |
|
| 369 |
if (fstat(fd, &st) == -1) { |
| 370 |
ret = errno; |
| 371 |
goto err; |
| 372 |
} |
| 373 |
|
| 374 |
if (st.st_size == 0) { |
| 375 |
ret = -1; /* no data -> no binary search */ |
| 376 |
goto err; |
| 377 |
} |
| 378 |
|
| 379 |
/* Validate / default arguments */ |
| 380 |
if (max_sz == 0) |
| 381 |
max_sz = DEFAULT_MAX_FILE_SIZE; |
| 382 |
for (i = page_sz; i; i >>= 1) { |
| 383 |
/* Make sure page_sz is a power of two */ |
| 384 |
if ((i % 2) && (i >> 1)) { |
| 385 |
page_sz = 0; |
| 386 |
break; |
| 387 |
} |
| 388 |
} |
| 389 |
if (page_sz == 0) |
| 390 |
#ifdef HAVE_STRUCT_STAT_ST_BLKSIZE |
| 391 |
page_sz = st.st_blksize; |
| 392 |
#else |
| 393 |
page_sz = 4096; |
| 394 |
#endif |
| 395 |
for (i = page_sz; i; i >>= 1) { |
| 396 |
/* Make sure page_sz is a power of two */ |
| 397 |
if ((i % 2) && (i >> 1)) { |
| 398 |
/* Can't happen! Filesystems always use powers of two! */ |
| 399 |
page_sz = 4096; |
| 400 |
break; |
| 401 |
} |
| 402 |
} |
| 403 |
if (page_sz > MAX_BLOCK_SIZE) |
| 404 |
page_sz = MAX_BLOCK_SIZE; |
| 405 |
|
| 406 |
new_bfh = calloc(1, sizeof (*new_bfh)); |
| 407 |
if (new_bfh == NULL) { |
| 408 |
ret = ENOMEM; |
| 409 |
goto err; |
| 410 |
} |
| 411 |
|
| 412 |
new_bfh->fd = fd; |
| 413 |
new_bfh->page_sz = page_sz; |
| 414 |
new_bfh->file_sz = st.st_size; |
| 415 |
|
| 416 |
if (max_sz >= st.st_size) { |
| 417 |
/* Whole-file method */ |
| 418 |
new_bfh->cache = malloc(st.st_size + 1); |
| 419 |
if (new_bfh->cache) { |
| 420 |
new_bfh->cache[st.st_size] = '\0'; |
| 421 |
new_bfh->cache_sz = st.st_size; |
| 422 |
ret = read(fd, new_bfh->cache, st.st_size); |
| 423 |
if (ret < 0) { |
| 424 |
ret = errno; |
| 425 |
goto err; |
| 426 |
} |
| 427 |
if (ret != st.st_size) { |
| 428 |
ret = EIO; /* XXX ??? */ |
| 429 |
goto err; |
| 430 |
} |
| 431 |
if (reads) |
| 432 |
*reads = 1; |
| 433 |
(void) close(fd); |
| 434 |
new_bfh->fd = -1; |
| 435 |
*bfh = new_bfh; |
| 436 |
return 0; |
| 437 |
} |
| 438 |
} |
| 439 |
|
| 440 |
/* Block-size method, or above malloc() failed */ |
| 441 |
new_bfh->page = malloc(new_bfh->page_sz << 1); |
| 442 |
if (new_bfh->page == NULL) { |
| 443 |
/* Can't even allocate a single double-size page! */ |
| 444 |
ret = ENOMEM; |
| 445 |
goto err; |
| 446 |
} |
| 447 |
|
| 448 |
new_bfh->cache_sz = max_sz < st.st_size ? max_sz : st.st_size; |
| 449 |
new_bfh->cache = malloc(new_bfh->cache_sz); |
| 450 |
*bfh = new_bfh; |
| 451 |
|
| 452 |
/* |
| 453 |
* malloc() may have failed because we were asking for a lot of |
| 454 |
* memory, but we may still be able to operate without a cache, |
| 455 |
* so let's not fail. |
| 456 |
*/ |
| 457 |
if (new_bfh->cache == NULL) { |
| 458 |
new_bfh->cache_sz = 0; |
| 459 |
return 0; |
| 460 |
} |
| 461 |
|
| 462 |
/* Initialize cache */ |
| 463 |
for (i = 0; i < new_bfh->cache_sz; i += new_bfh->page_sz) |
| 464 |
new_bfh->cache[i] = '\0'; |
| 465 |
return 0; |
| 466 |
|
| 467 |
err: |
| 468 |
(void) close(fd); |
| 469 |
if (new_bfh) { |
| 470 |
free(new_bfh->page); |
| 471 |
free(new_bfh->cache); |
| 472 |
free(new_bfh); |
| 473 |
} |
| 474 |
return ret; |
| 475 |
} |
| 476 |
|
| 477 |
/* |
| 478 |
* Indicate whether the given binary search file handle will be searched |
| 479 |
* with block-wise method. |
| 480 |
*/ |
| 481 |
void |
| 482 |
_bsearch_file_info(bsearch_file_handle bfh, |
| 483 |
size_t *page_sz, size_t *max_sz, int *blockwise) |
| 484 |
{ |
| 485 |
if (page_sz) |
| 486 |
*page_sz = bfh->page_sz; |
| 487 |
if (max_sz) |
| 488 |
*max_sz = bfh->cache_sz; |
| 489 |
if (blockwise) |
| 490 |
*blockwise = (bfh->file_sz != bfh->cache_sz); |
| 491 |
} |
| 492 |
|
| 493 |
/* |
| 494 |
* Close the given binary file search handle. |
| 495 |
* |
| 496 |
* Inputs: |
| 497 |
* |
| 498 |
* @bfh Pointer to variable containing handle to close. |
| 499 |
*/ |
| 500 |
void |
| 501 |
_bsearch_file_close(bsearch_file_handle *bfh) |
| 502 |
{ |
| 503 |
if (!*bfh) |
| 504 |
return; |
| 505 |
if ((*bfh)->fd >= 0) |
| 506 |
(void) close((*bfh)->fd); |
| 507 |
if ((*bfh)->page) |
| 508 |
free((*bfh)->page); |
| 509 |
if ((*bfh)->cache) |
| 510 |
free((*bfh)->cache); |
| 511 |
free(*bfh); |
| 512 |
*bfh = NULL; |
| 513 |
} |
| 514 |
|
| 515 |
/* |
| 516 |
* Private function to get a page from a cache. The cache is a char |
| 517 |
* array of 2^n - 1 double-size page worth of bytes, where n is the |
| 518 |
* number of tree levels that the cache stores. The cache can be |
| 519 |
* smaller than n implies. |
| 520 |
* |
| 521 |
* The page may or may not be valid. If the first byte of it is NUL |
| 522 |
* then it's not valid, else it is. |
| 523 |
* |
| 524 |
* Returns 1 if page is in cache and valid, 0 if the cache is too small |
| 525 |
* or the page is invalid. The page address is output in @buf if the |
| 526 |
* cache is large enough to contain it regardless of whether the page is |
| 527 |
* valid. |
| 528 |
* |
| 529 |
* Inputs: |
| 530 |
* |
| 531 |
* @bfh Binary search file handle |
| 532 |
* @level Level in the tree that we want a page for |
| 533 |
* @page_idx Page number in the given level (0..2^level - 1) |
| 534 |
* |
| 535 |
* Outputs: |
| 536 |
* |
| 537 |
* @buf Set to address of page if the cache is large enough |
| 538 |
*/ |
| 539 |
static int |
| 540 |
get_page_from_cache(bsearch_file_handle bfh, size_t level, size_t page_idx, |
| 541 |
char **buf) |
| 542 |
{ |
| 543 |
size_t idx = 0; |
| 544 |
size_t page_sz; |
| 545 |
|
| 546 |
page_sz = bfh->page_sz << 1; /* we use double-size pages in the cache */ |
| 547 |
|
| 548 |
*buf = NULL; |
| 549 |
|
| 550 |
/* |
| 551 |
* Compute index into cache. The cache is basically an array of |
| 552 |
* double-size pages. The first (zeroth) double-size page in the |
| 553 |
* cache will be the middle page of the file -- the root of the |
| 554 |
* tree. The next two double-size pages will be the left and right |
| 555 |
* pages of the second level in the tree. The next four double-size |
| 556 |
* pages will be the four pages at the next level. And so on for as |
| 557 |
* many pages as fit in the cache. |
| 558 |
* |
| 559 |
* The page index is the number of the page at the given level. We |
| 560 |
* then compute (2^level - 1 + page index) * 2page size, check that |
| 561 |
* we have that in the cache, check that the page has been read (it |
| 562 |
* doesn't start with NUL). |
| 563 |
*/ |
| 564 |
if (level) |
| 565 |
idx = (1 << level) - 1 + page_idx; |
| 566 |
if (((idx + 1) * page_sz * 2) > bfh->cache_sz) |
| 567 |
return 0; |
| 568 |
|
| 569 |
*buf = &bfh->cache[idx * page_sz * 2]; |
| 570 |
if (bfh->cache[idx * page_sz * 2] == '\0') |
| 571 |
return 0; /* cache[idx] == NUL -> page not loaded in cache */ |
| 572 |
return 1; |
| 573 |
} |
| 574 |
|
| 575 |
/* |
| 576 |
* Private function to read a page of @page_sz from @fd at offset @off |
| 577 |
* into @buf, outputing the number of bytes read, which will be the same |
| 578 |
* as @page_sz unless the page being read is the last page, in which |
| 579 |
* case the number of remaining bytes in the file will be output. |
| 580 |
* |
| 581 |
* Returns 0 on success or an errno value otherwise (EIO if reads are |
| 582 |
* short). |
| 583 |
* |
| 584 |
* Inputs: |
| 585 |
* |
| 586 |
* @bfh Binary search file handle |
| 587 |
* @level Level in the binary search tree that we're at |
| 588 |
* @page_idx Page "index" at the @level of the tree that we want |
| 589 |
* @page Actual page number that we want |
| 590 |
* want_double Whether we need a page or double page read |
| 591 |
* |
| 592 |
* Outputs: |
| 593 |
* |
| 594 |
* @buf Page read or cached |
| 595 |
* @bytes Bytes read (may be less than page or double page size in |
| 596 |
* the case of the last page, of course) |
| 597 |
*/ |
| 598 |
static int |
| 599 |
read_page(bsearch_file_handle bfh, size_t level, size_t page_idx, size_t page, |
| 600 |
int want_double, const char **buf, size_t *bytes) |
| 601 |
{ |
| 602 |
int ret; |
| 603 |
off_t off; |
| 604 |
size_t expected; |
| 605 |
size_t wanted; |
| 606 |
char *page_buf; |
| 607 |
|
| 608 |
/* Figure out where we're reading and how much */ |
| 609 |
off = page * bfh->page_sz; |
| 610 |
if (off < 0) |
| 611 |
return EOVERFLOW; |
| 612 |
|
| 613 |
wanted = bfh->page_sz << want_double; |
| 614 |
expected = ((bfh->file_sz - off) > wanted) ? wanted : bfh->file_sz - off; |
| 615 |
|
| 616 |
if (get_page_from_cache(bfh, level, page_idx, &page_buf)) { |
| 617 |
*buf = page_buf; |
| 618 |
*bytes = expected; |
| 619 |
return 0; /* found in cache */ |
| 620 |
} |
| 621 |
|
| 622 |
|
| 623 |
*bytes = 0; |
| 624 |
*buf = NULL; |
| 625 |
|
| 626 |
/* OK, we have to read a page or double-size page */ |
| 627 |
|
| 628 |
if (page_buf) |
| 629 |
want_double = 1; /* we'll be caching; we cache double-size pages */ |
| 630 |
else |
| 631 |
page_buf = bfh->page; /* we won't cache this page */ |
| 632 |
|
| 633 |
wanted = bfh->page_sz << want_double; |
| 634 |
expected = ((bfh->file_sz - off) > wanted) ? wanted : bfh->file_sz - off; |
| 635 |
|
| 636 |
#ifdef HAVE_PREAD |
| 637 |
ret = pread(bfh->fd, page_buf, expected, off); |
| 638 |
#else |
| 639 |
if (lseek(bfh->fd, off, SEEK_SET) == (off_t)-1) |
| 640 |
return errno; |
| 641 |
ret = read(bfh->fd, page_buf, expected); |
| 642 |
#endif |
| 643 |
if (ret < 0) |
| 644 |
return errno; |
| 645 |
|
| 646 |
if (ret != expected) |
| 647 |
return EIO; /* XXX ??? */ |
| 648 |
|
| 649 |
*buf = page_buf; |
| 650 |
*bytes = expected; |
| 651 |
return 0; |
| 652 |
} |
| 653 |
|
| 654 |
/* |
| 655 |
* Perform a binary search of a file where each line is a record (LF and |
| 656 |
* CRLF supported). Each record consists of a key followed by an |
| 657 |
* optional value separated from the key by whitespace. Whitespace can |
| 658 |
* be quoted with backslashes. It's the caller's responsibility to |
| 659 |
* encode/decode keys/values if quoting is desired; newlines should be |
| 660 |
* encoded such that a newline does not appear in the result. |
| 661 |
* |
| 662 |
* The search is done with block-wise I/O (i.e., the whole file is not |
| 663 |
* read into memory). |
| 664 |
* |
| 665 |
* All output arguments are optional. |
| 666 |
* |
| 667 |
* Returns 0 if key is found, -1 if not found, or an error code such as |
| 668 |
* ENOMEM in case of error. |
| 669 |
* |
| 670 |
* NOTE: We could improve this by not freeing the buffer, instead |
| 671 |
* requiring that the caller provide it. Further, we could cache |
| 672 |
* the top N levels of [double-size] pages (2^N - 1 pages), which |
| 673 |
* should speed up most searches by reducing the number of reads |
| 674 |
* by N. |
| 675 |
* |
| 676 |
* Inputs: |
| 677 |
* |
| 678 |
* @fd File descriptor (file to search) |
| 679 |
* @page_sz Page size (if zero then the file's st_blksize will be used) |
| 680 |
* @key Key string to search for |
| 681 |
* |
| 682 |
* Outputs: |
| 683 |
* |
| 684 |
* @value Location to store a copy of the value (caller must free) |
| 685 |
* @location Record location if found else the location where the |
| 686 |
* record should be inserted (index into @buf) |
| 687 |
* @loops Location to store a count of bisections required for |
| 688 |
* search (useful for confirming logarithmic performance) |
| 689 |
* @reads Location to store a count of pages read during search |
| 690 |
* (useful for confirming logarithmic performance) |
| 691 |
*/ |
| 692 |
int |
| 693 |
_bsearch_file(bsearch_file_handle bfh, const char *key, |
| 694 |
char **value, size_t *location, size_t *loops, size_t *reads) |
| 695 |
{ |
| 696 |
int ret; |
| 697 |
const char *buf; |
| 698 |
size_t buf_sz; |
| 699 |
size_t page, l, r; |
| 700 |
size_t my_reads = 0; |
| 701 |
size_t my_loops_total = 0; |
| 702 |
size_t my_loops; |
| 703 |
size_t level; /* level in the tree */ |
| 704 |
size_t page_idx = 0; /* page number in the tree level */ |
| 705 |
size_t buf_location; |
| 706 |
int cmp; |
| 707 |
int buf_ends_in_eol = 0; |
| 708 |
int buf_is_start = 0; |
| 709 |
|
| 710 |
if (reads) |
| 711 |
*reads = 0; |
| 712 |
if (value) |
| 713 |
*value = NULL; |
| 714 |
if (loops) |
| 715 |
*loops = 0; |
| 716 |
|
| 717 |
/* If whole file is in memory then search that and we're done */ |
| 718 |
if (bfh->file_sz == bfh->cache_sz) |
| 719 |
return _bsearch_text(bfh->cache, bfh->cache_sz, key, value, location, loops); |
| 720 |
|
| 721 |
/* Else block-wise binary search */ |
| 722 |
|
| 723 |
l = 0; |
| 724 |
r = (bfh->file_sz / bfh->page_sz) + 1; |
| 725 |
for (level = 0, page = r >> 1; page >= l && page < r ; level++) { |
| 726 |
ret = read_page(bfh, level, page_idx, page, 0, &buf, &buf_sz); |
| 727 |
if (ret != 0) |
| 728 |
return ret; |
| 729 |
my_reads++; |
| 730 |
if (buf[buf_sz - 1] == '\r' || buf[buf_sz - 1] == '\n') |
| 731 |
buf_ends_in_eol = 1; |
| 732 |
else |
| 733 |
buf_ends_in_eol = 0; |
| 734 |
|
| 735 |
buf_is_start = page == 0 ? 1 : 0; |
| 736 |
ret = bsearch_common(buf, (size_t)buf_sz, key, buf_is_start, |
| 737 |
value, &buf_location, &cmp, &my_loops); |
| 738 |
if (ret > 0) |
| 739 |
return ret; |
| 740 |
/* Found or no we update stats */ |
| 741 |
my_loops_total += my_loops; |
| 742 |
if (loops) |
| 743 |
*loops = my_loops_total; |
| 744 |
if (reads) |
| 745 |
*reads = my_reads; |
| 746 |
if (location) |
| 747 |
*location = page * bfh->page_sz + buf_location; |
| 748 |
if (ret == 0) |
| 749 |
return 0; /* found! */ |
| 750 |
/* Not found */ |
| 751 |
if (cmp < 0) { |
| 752 |
/* Search left */ |
| 753 |
page_idx <<= 1; |
| 754 |
r = page; |
| 755 |
page = l + ((r - l) >> 1); |
| 756 |
continue; |
| 757 |
} else { |
| 758 |
/* |
| 759 |
* Search right, but first search the current and next |
| 760 |
* blocks in case that the record we're looking for either |
| 761 |
* straddles the boundary between this and the next record, |
| 762 |
* or in case the record starts exactly at the next page. |
| 763 |
*/ |
| 764 |
heim_assert(cmp > 0, "cmp > 0"); |
| 765 |
|
| 766 |
if (!buf_ends_in_eol || page == l || page == (r - 1)) { |
| 767 |
ret = read_page(bfh, level, page_idx, page, 1, &buf, &buf_sz); |
| 768 |
if (ret != 0) |
| 769 |
return ret; |
| 770 |
my_reads++; |
| 771 |
|
| 772 |
buf_is_start = page == l ? 1 : 0; |
| 773 |
|
| 774 |
ret = bsearch_common(buf, (size_t)buf_sz, key, buf_is_start, |
| 775 |
value, &buf_location, &cmp, &my_loops); |
| 776 |
if (ret > 0) |
| 777 |
return ret; |
| 778 |
my_loops_total += my_loops; |
| 779 |
if (loops) |
| 780 |
*loops = my_loops_total; |
| 781 |
if (reads) |
| 782 |
*reads = my_reads; |
| 783 |
if (location) |
| 784 |
*location = page * bfh->page_sz + buf_location; |
| 785 |
if (ret == 0) |
| 786 |
return 0; |
| 787 |
} |
| 788 |
|
| 789 |
/* Oh well, search right */ |
| 790 |
if (l == page && r == (l + 1)) |
| 791 |
break; |
| 792 |
page_idx = (page_idx << 1) + 1; |
| 793 |
l = page; |
| 794 |
page = l + ((r - l) >> 1); |
| 795 |
continue; |
| 796 |
} |
| 797 |
} |
| 798 |
return -1; |
| 799 |
} |
| 800 |
|
| 801 |
|
| 802 |
static int |
| 803 |
stdb_open(void *plug, const char *dbtype, const char *dbname, |
| 804 |
heim_dict_t options, void **db, heim_error_t *error) |
| 805 |
{ |
| 806 |
bsearch_file_handle bfh; |
| 807 |
char *p; |
| 808 |
int ret; |
| 809 |
|
| 810 |
if (error) |
| 811 |
*error = NULL; |
| 812 |
if (dbname == NULL || *dbname == '\0') { |
| 813 |
if (error) |
| 814 |
*error = heim_error_create(EINVAL, |
| 815 |
N_("DB name required for sorted-text DB " |
| 816 |
"plugin", "")); |
| 817 |
return EINVAL; |
| 818 |
} |
| 819 |
p = strrchr(dbname, '.'); |
| 820 |
if (p == NULL || strcmp(p, ".txt") != 0) { |
| 821 |
if (error) |
| 822 |
*error = heim_error_create(ENOTSUP, |
| 823 |
N_("Text file (name ending in .txt) " |
| 824 |
"required for sorted-text DB plugin", |
| 825 |
"")); |
| 826 |
return ENOTSUP; |
| 827 |
} |
| 828 |
|
| 829 |
ret = _bsearch_file_open(dbname, 0, 0, &bfh, NULL); |
| 830 |
if (ret) |
| 831 |
return ret; |
| 832 |
|
| 833 |
*db = bfh; |
| 834 |
return 0; |
| 835 |
} |
| 836 |
|
| 837 |
static int |
| 838 |
stdb_close(void *db, heim_error_t *error) |
| 839 |
{ |
| 840 |
bsearch_file_handle bfh = db; |
| 841 |
|
| 842 |
if (error) |
| 843 |
*error = NULL; |
| 844 |
_bsearch_file_close(&bfh); |
| 845 |
return 0; |
| 846 |
} |
| 847 |
|
| 848 |
static heim_data_t |
| 849 |
stdb_copy_value(void *db, heim_string_t table, heim_data_t key, |
| 850 |
heim_error_t *error) |
| 851 |
{ |
| 852 |
bsearch_file_handle bfh = db; |
| 853 |
const char *k; |
| 854 |
char *v = NULL; |
| 855 |
heim_data_t value; |
| 856 |
int ret; |
| 857 |
|
| 858 |
if (error) |
| 859 |
*error = NULL; |
| 860 |
|
| 861 |
if (table == NULL) |
| 862 |
table = HSTR(""); |
| 863 |
|
| 864 |
if (table != HSTR("")) |
| 865 |
return NULL; |
| 866 |
|
| 867 |
if (heim_get_tid(key) == HEIM_TID_STRING) |
| 868 |
k = heim_string_get_utf8((heim_string_t)key); |
| 869 |
else |
| 870 |
k = (const char *)heim_data_get_ptr(key); |
| 871 |
ret = _bsearch_file(bfh, k, &v, NULL, NULL, NULL); |
| 872 |
if (ret == 0 && v == NULL) |
| 873 |
ret = -1; /* Quiet lint */ |
| 874 |
if (ret != 0) { |
| 875 |
if (ret > 0 && error) |
| 876 |
*error = heim_error_create(ret, "%s", strerror(ret)); |
| 877 |
return NULL; |
| 878 |
} |
| 879 |
value = heim_data_create(v, strlen(v)); |
| 880 |
free(v); |
| 881 |
/* XXX Handle ENOMEM */ |
| 882 |
return value; |
| 883 |
} |
| 884 |
|
| 885 |
struct heim_db_type heim_sorted_text_file_dbtype = { |
| 886 |
1, stdb_open, NULL, stdb_close, NULL, NULL, NULL, NULL, NULL, NULL, |
| 887 |
stdb_copy_value, NULL, NULL, NULL |
| 888 |
}; |