|
rpm-build |
ca8475 |
/*
|
|
rpm-build |
ca8475 |
Unix SMB/CIFS implementation.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
trivial database library
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
Copyright (C) Rusty Russell 2009
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
** NOTE! The following LGPL license applies to the tdb
|
|
rpm-build |
ca8475 |
** library. This does NOT imply that all of Samba is released
|
|
rpm-build |
ca8475 |
** under the LGPL
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
This library is free software; you can redistribute it and/or
|
|
rpm-build |
ca8475 |
modify it under the terms of the GNU Lesser General Public
|
|
rpm-build |
ca8475 |
License as published by the Free Software Foundation; either
|
|
rpm-build |
ca8475 |
version 3 of the License, or (at your option) any later version.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
This library is distributed in the hope that it will be useful,
|
|
rpm-build |
ca8475 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
rpm-build |
ca8475 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
rpm-build |
ca8475 |
Lesser General Public License for more details.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
You should have received a copy of the GNU Lesser General Public
|
|
rpm-build |
ca8475 |
License along with this library; if not, see <http://www.gnu.org/licenses/>.
|
|
rpm-build |
ca8475 |
*/
|
|
rpm-build |
ca8475 |
#include "tdb_private.h"
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Since we opened it, these shouldn't fail unless it's recent corruption. */
|
|
rpm-build |
ca8475 |
static bool tdb_check_header(struct tdb_context *tdb, tdb_off_t *recovery)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
struct tdb_header hdr;
|
|
rpm-build |
ca8475 |
uint32_t h1, h2;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (tdb->methods->tdb_read(tdb, 0, &hdr, sizeof(hdr), 0) == -1)
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
if (strcmp(hdr.magic_food, TDB_MAGIC_FOOD) != 0)
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
CONVERT(hdr);
|
|
rpm-build |
ca8475 |
if (hdr.version != TDB_VERSION)
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (hdr.rwlocks != 0 &&
|
|
rpm-build |
ca8475 |
hdr.rwlocks != TDB_FEATURE_FLAG_MAGIC &&
|
|
rpm-build |
ca8475 |
hdr.rwlocks != TDB_HASH_RWLOCK_MAGIC)
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
tdb_header_hash(tdb, &h1, &h2;;
|
|
rpm-build |
ca8475 |
if (hdr.magic1_hash && hdr.magic2_hash &&
|
|
rpm-build |
ca8475 |
(hdr.magic1_hash != h1 || hdr.magic2_hash != h2))
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (hdr.hash_size == 0)
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (hdr.hash_size != tdb->hash_size)
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (hdr.recovery_start != 0 &&
|
|
rpm-build |
ca8475 |
hdr.recovery_start < TDB_DATA_START(tdb->hash_size))
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
*recovery = hdr.recovery_start;
|
|
rpm-build |
ca8475 |
return true;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
corrupt:
|
|
rpm-build |
ca8475 |
tdb->ecode = TDB_ERR_CORRUPT;
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR, "Header is corrupt\n"));
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Generic record header check. */
|
|
rpm-build |
ca8475 |
static bool tdb_check_record(struct tdb_context *tdb,
|
|
rpm-build |
ca8475 |
tdb_off_t off,
|
|
rpm-build |
ca8475 |
const struct tdb_record *rec)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
tdb_off_t tailer;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Check rec->next: 0 or points to record offset, aligned. */
|
|
rpm-build |
ca8475 |
if (rec->next > 0 && rec->next < TDB_DATA_START(tdb->hash_size)){
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u too small next %u\n",
|
|
rpm-build |
ca8475 |
off, rec->next));
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
if (rec->next + sizeof(*rec) < rec->next) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u too large next %u\n",
|
|
rpm-build |
ca8475 |
off, rec->next));
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
if ((rec->next % TDB_ALIGNMENT) != 0) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u misaligned next %u\n",
|
|
rpm-build |
ca8475 |
off, rec->next));
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
if (tdb_oob(tdb, rec->next, sizeof(*rec), 0))
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Check rec_len: similar to rec->next, implies next record. */
|
|
rpm-build |
ca8475 |
if ((rec->rec_len % TDB_ALIGNMENT) != 0) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u misaligned length %u\n",
|
|
rpm-build |
ca8475 |
off, rec->rec_len));
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
/* Must fit tailer. */
|
|
rpm-build |
ca8475 |
if (rec->rec_len < sizeof(tailer)) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u too short length %u\n",
|
|
rpm-build |
ca8475 |
off, rec->rec_len));
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
/* OOB allows "right at the end" access, so this works for last rec. */
|
|
rpm-build |
ca8475 |
if (tdb_oob(tdb, off, sizeof(*rec)+rec->rec_len, 0))
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Check tailer. */
|
|
rpm-build |
ca8475 |
if (tdb_ofs_read(tdb, off+sizeof(*rec)+rec->rec_len-sizeof(tailer),
|
|
rpm-build |
ca8475 |
&tailer) == -1)
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
if (tailer != sizeof(*rec) + rec->rec_len) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u invalid tailer\n", off));
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
return true;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
corrupt:
|
|
rpm-build |
ca8475 |
tdb->ecode = TDB_ERR_CORRUPT;
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Grab some bytes: may copy if can't use mmap.
|
|
rpm-build |
ca8475 |
Caller has already done bounds check. */
|
|
rpm-build |
ca8475 |
static TDB_DATA get_bytes(struct tdb_context *tdb,
|
|
rpm-build |
ca8475 |
tdb_off_t off, tdb_len_t len)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
TDB_DATA d;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
d.dsize = len;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (tdb->transaction == NULL && tdb->map_ptr != NULL)
|
|
rpm-build |
ca8475 |
d.dptr = (unsigned char *)tdb->map_ptr + off;
|
|
rpm-build |
ca8475 |
else
|
|
rpm-build |
ca8475 |
d.dptr = tdb_alloc_read(tdb, off, d.dsize);
|
|
rpm-build |
ca8475 |
return d;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Frees data if we're not able to simply use mmap. */
|
|
rpm-build |
ca8475 |
static void put_bytes(struct tdb_context *tdb, TDB_DATA d)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
if (tdb->transaction == NULL && tdb->map_ptr != NULL)
|
|
rpm-build |
ca8475 |
return;
|
|
rpm-build |
ca8475 |
free(d.dptr);
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
|
|
rpm-build |
ca8475 |
* See: http://burtleburtle.net/bob/c/lookup3.c
|
|
rpm-build |
ca8475 |
*/
|
|
rpm-build |
ca8475 |
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
|
|
rpm-build |
ca8475 |
static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
uint32_t a,b,c;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Set up the internal state */
|
|
rpm-build |
ca8475 |
a = b = c = 0xdeadbeef + *pc;
|
|
rpm-build |
ca8475 |
c += *pb;
|
|
rpm-build |
ca8475 |
a += key;
|
|
rpm-build |
ca8475 |
c ^= b; c -= rot(b,14);
|
|
rpm-build |
ca8475 |
a ^= c; a -= rot(c,11);
|
|
rpm-build |
ca8475 |
b ^= a; b -= rot(a,25);
|
|
rpm-build |
ca8475 |
c ^= b; c -= rot(b,16);
|
|
rpm-build |
ca8475 |
a ^= c; a -= rot(c,4);
|
|
rpm-build |
ca8475 |
b ^= a; b -= rot(a,14);
|
|
rpm-build |
ca8475 |
c ^= b; c -= rot(b,24);
|
|
rpm-build |
ca8475 |
*pc=c; *pb=b;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/*
|
|
rpm-build |
ca8475 |
We want to check that all free records are in the free list
|
|
rpm-build |
ca8475 |
(only once), and all free list entries are free records. Similarly
|
|
rpm-build |
ca8475 |
for each hash chain of used records.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
Doing that naively (without walking hash chains, since we want to be
|
|
rpm-build |
ca8475 |
linear) means keeping a list of records which have been seen in each
|
|
rpm-build |
ca8475 |
hash chain, and another of records pointed to (ie. next pointers
|
|
rpm-build |
ca8475 |
from records and the initial hash chain heads). These two lists
|
|
rpm-build |
ca8475 |
should be equal. This will take 8 bytes per record, and require
|
|
rpm-build |
ca8475 |
sorting at the end.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
So instead, we record each offset in a bitmap such a way that
|
|
rpm-build |
ca8475 |
recording it twice will cancel out. Since each offset should appear
|
|
rpm-build |
ca8475 |
exactly twice, the bitmap should be zero at the end.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
The approach was inspired by Bloom Filters (see Wikipedia). For
|
|
rpm-build |
ca8475 |
each value, we flip K bits in a bitmap of size N. The number of
|
|
rpm-build |
ca8475 |
distinct arrangements is:
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
N! / (K! * (N-K)!)
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
Of course, not all arrangements are actually distinct, but testing
|
|
rpm-build |
ca8475 |
shows this formula to be close enough.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
So, if K == 8 and N == 256, the probability of two things flipping the same
|
|
rpm-build |
ca8475 |
bits is 1 in 409,663,695,276,000.
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
Given that ldb uses a hash size of 10000, using 32 bytes per hash chain
|
|
rpm-build |
ca8475 |
(320k) seems reasonable.
|
|
rpm-build |
ca8475 |
*/
|
|
rpm-build |
ca8475 |
#define NUM_HASHES 8
|
|
rpm-build |
ca8475 |
#define BITMAP_BITS 256
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
static void bit_flip(unsigned char bits[], unsigned int idx)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* We record offsets in a bitmap for the particular chain it should be in. */
|
|
rpm-build |
ca8475 |
static void record_offset(unsigned char bits[], tdb_off_t off)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
uint32_t h1 = off, h2 = 0;
|
|
rpm-build |
ca8475 |
unsigned int i;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* We get two good hash values out of jhash2, so we use both. Then
|
|
rpm-build |
ca8475 |
* we keep going to produce further hash values. */
|
|
rpm-build |
ca8475 |
for (i = 0; i < NUM_HASHES / 2; i++) {
|
|
rpm-build |
ca8475 |
hash(off, &h1, &h2;;
|
|
rpm-build |
ca8475 |
bit_flip(bits, h1 % BITMAP_BITS);
|
|
rpm-build |
ca8475 |
bit_flip(bits, h2 % BITMAP_BITS);
|
|
rpm-build |
ca8475 |
h2++;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Check that an in-use record is valid. */
|
|
rpm-build |
ca8475 |
static bool tdb_check_used_record(struct tdb_context *tdb,
|
|
rpm-build |
ca8475 |
tdb_off_t off,
|
|
rpm-build |
ca8475 |
const struct tdb_record *rec,
|
|
rpm-build |
ca8475 |
unsigned char **hashes,
|
|
rpm-build |
ca8475 |
int (*check)(TDB_DATA, TDB_DATA, void *),
|
|
rpm-build |
ca8475 |
void *private_data)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
TDB_DATA key, data;
|
|
rpm-build |
ca8475 |
tdb_len_t len;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (!tdb_check_record(tdb, off, rec))
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* key + data + tailer must fit in record */
|
|
rpm-build |
ca8475 |
len = rec->key_len;
|
|
rpm-build |
ca8475 |
len += rec->data_len;
|
|
rpm-build |
ca8475 |
if (len < rec->data_len) {
|
|
rpm-build |
ca8475 |
/* overflow */
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR, "Record lengths overflow\n"));
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
len += sizeof(tdb_off_t);
|
|
rpm-build |
ca8475 |
if (len < sizeof(tdb_off_t)) {
|
|
rpm-build |
ca8475 |
/* overflow */
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR, "Record lengths overflow\n"));
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (len > rec->rec_len) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u too short for contents\n", off));
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
key = get_bytes(tdb, off + sizeof(*rec), rec->key_len);
|
|
rpm-build |
ca8475 |
if (!key.dptr)
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (tdb->hash_fn(&key) != rec->full_hash) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Record offset %u has incorrect hash\n", off));
|
|
rpm-build |
ca8475 |
goto fail_put_key;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Mark this offset as a known value for this hash bucket. */
|
|
rpm-build |
ca8475 |
record_offset(hashes[BUCKET(rec->full_hash)+1], off);
|
|
rpm-build |
ca8475 |
/* And similarly if the next pointer is valid. */
|
|
rpm-build |
ca8475 |
if (rec->next)
|
|
rpm-build |
ca8475 |
record_offset(hashes[BUCKET(rec->full_hash)+1], rec->next);
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* If they supply a check function and this record isn't dead,
|
|
rpm-build |
ca8475 |
get data and feed it. */
|
|
rpm-build |
ca8475 |
if (check && rec->magic != TDB_DEAD_MAGIC) {
|
|
rpm-build |
ca8475 |
data = get_bytes(tdb, off + sizeof(*rec) + rec->key_len,
|
|
rpm-build |
ca8475 |
rec->data_len);
|
|
rpm-build |
ca8475 |
if (!data.dptr)
|
|
rpm-build |
ca8475 |
goto fail_put_key;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
if (check(key, data, private_data) == -1)
|
|
rpm-build |
ca8475 |
goto fail_put_data;
|
|
rpm-build |
ca8475 |
put_bytes(tdb, data);
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
put_bytes(tdb, key);
|
|
rpm-build |
ca8475 |
return true;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
fail_put_data:
|
|
rpm-build |
ca8475 |
put_bytes(tdb, data);
|
|
rpm-build |
ca8475 |
fail_put_key:
|
|
rpm-build |
ca8475 |
put_bytes(tdb, key);
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Check that an unused record is valid. */
|
|
rpm-build |
ca8475 |
static bool tdb_check_free_record(struct tdb_context *tdb,
|
|
rpm-build |
ca8475 |
tdb_off_t off,
|
|
rpm-build |
ca8475 |
const struct tdb_record *rec,
|
|
rpm-build |
ca8475 |
unsigned char **hashes)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
if (!tdb_check_record(tdb, off, rec))
|
|
rpm-build |
ca8475 |
return false;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Mark this offset as a known value for the free list. */
|
|
rpm-build |
ca8475 |
record_offset(hashes[0], off);
|
|
rpm-build |
ca8475 |
/* And similarly if the next pointer is valid. */
|
|
rpm-build |
ca8475 |
if (rec->next)
|
|
rpm-build |
ca8475 |
record_offset(hashes[0], rec->next);
|
|
rpm-build |
ca8475 |
return true;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Slow, but should be very rare. */
|
|
rpm-build |
ca8475 |
size_t tdb_dead_space(struct tdb_context *tdb, tdb_off_t off)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
size_t len;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
for (len = 0; off + len < tdb->map_size; len++) {
|
|
rpm-build |
ca8475 |
char c;
|
|
rpm-build |
ca8475 |
if (tdb->methods->tdb_read(tdb, off, &c, 1, 0))
|
|
rpm-build |
ca8475 |
return 0;
|
|
rpm-build |
ca8475 |
if (c != 0 && c != 0x42)
|
|
rpm-build |
ca8475 |
break;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
return len;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
_PUBLIC_ int tdb_check(struct tdb_context *tdb,
|
|
rpm-build |
ca8475 |
int (*check)(TDB_DATA key, TDB_DATA data, void *private_data),
|
|
rpm-build |
ca8475 |
void *private_data)
|
|
rpm-build |
ca8475 |
{
|
|
rpm-build |
ca8475 |
unsigned int h;
|
|
rpm-build |
ca8475 |
unsigned char **hashes;
|
|
rpm-build |
ca8475 |
tdb_off_t off, recovery_start;
|
|
rpm-build |
ca8475 |
struct tdb_record rec;
|
|
rpm-build |
ca8475 |
bool found_recovery = false;
|
|
rpm-build |
ca8475 |
tdb_len_t dead;
|
|
rpm-build |
ca8475 |
bool locked;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Read-only databases use no locking at all: it's best-effort.
|
|
rpm-build |
ca8475 |
* We may have a write lock already, so skip that case too. */
|
|
rpm-build |
ca8475 |
if (tdb->read_only || tdb->allrecord_lock.count != 0) {
|
|
rpm-build |
ca8475 |
locked = false;
|
|
rpm-build |
ca8475 |
} else {
|
|
rpm-build |
ca8475 |
if (tdb_lockall_read(tdb) == -1)
|
|
rpm-build |
ca8475 |
return -1;
|
|
rpm-build |
ca8475 |
locked = true;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Make sure we know true size of the underlying file. */
|
|
rpm-build |
ca8475 |
tdb_oob(tdb, tdb->map_size, 1, 1);
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Header must be OK: also gets us the recovery ptr, if any. */
|
|
rpm-build |
ca8475 |
if (!tdb_check_header(tdb, &recovery_start))
|
|
rpm-build |
ca8475 |
goto unlock;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* We should have the whole header, too. */
|
|
rpm-build |
ca8475 |
if (tdb->map_size < TDB_DATA_START(tdb->hash_size)) {
|
|
rpm-build |
ca8475 |
tdb->ecode = TDB_ERR_CORRUPT;
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR, "File too short for hashes\n"));
|
|
rpm-build |
ca8475 |
goto unlock;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* One big malloc: pointers then bit arrays. */
|
|
rpm-build |
ca8475 |
hashes = (unsigned char **)calloc(
|
|
rpm-build |
ca8475 |
1, sizeof(hashes[0]) * (1+tdb->hash_size)
|
|
rpm-build |
ca8475 |
+ BITMAP_BITS / CHAR_BIT * (1+tdb->hash_size));
|
|
rpm-build |
ca8475 |
if (!hashes) {
|
|
rpm-build |
ca8475 |
tdb->ecode = TDB_ERR_OOM;
|
|
rpm-build |
ca8475 |
goto unlock;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Initialize pointers */
|
|
rpm-build |
ca8475 |
hashes[0] = (unsigned char *)(&hashes[1+tdb->hash_size]);
|
|
rpm-build |
ca8475 |
for (h = 1; h < 1+tdb->hash_size; h++)
|
|
rpm-build |
ca8475 |
hashes[h] = hashes[h-1] + BITMAP_BITS / CHAR_BIT;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Freelist and hash headers are all in a row: read them. */
|
|
rpm-build |
ca8475 |
for (h = 0; h < 1+tdb->hash_size; h++) {
|
|
rpm-build |
ca8475 |
if (tdb_ofs_read(tdb, FREELIST_TOP + h*sizeof(tdb_off_t),
|
|
rpm-build |
ca8475 |
&off) == -1)
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
if (off)
|
|
rpm-build |
ca8475 |
record_offset(hashes[h], off);
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* For each record, read it in and check it's ok. */
|
|
rpm-build |
ca8475 |
for (off = TDB_DATA_START(tdb->hash_size);
|
|
rpm-build |
ca8475 |
off < tdb->map_size;
|
|
rpm-build |
ca8475 |
off += sizeof(rec) + rec.rec_len) {
|
|
rpm-build |
ca8475 |
if (tdb->methods->tdb_read(tdb, off, &rec, sizeof(rec),
|
|
rpm-build |
ca8475 |
DOCONV()) == -1)
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
switch (rec.magic) {
|
|
rpm-build |
ca8475 |
case TDB_MAGIC:
|
|
rpm-build |
ca8475 |
case TDB_DEAD_MAGIC:
|
|
rpm-build |
ca8475 |
if (!tdb_check_used_record(tdb, off, &rec, hashes,
|
|
rpm-build |
ca8475 |
check, private_data))
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
break;
|
|
rpm-build |
ca8475 |
case TDB_FREE_MAGIC:
|
|
rpm-build |
ca8475 |
if (!tdb_check_free_record(tdb, off, &rec, hashes))
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
break;
|
|
rpm-build |
ca8475 |
/* If we crash after ftruncate, we can get zeroes or fill. */
|
|
rpm-build |
ca8475 |
case TDB_RECOVERY_INVALID_MAGIC:
|
|
rpm-build |
ca8475 |
case 0x42424242:
|
|
rpm-build |
ca8475 |
if (recovery_start == off) {
|
|
rpm-build |
ca8475 |
found_recovery = true;
|
|
rpm-build |
ca8475 |
break;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
dead = tdb_dead_space(tdb, off);
|
|
rpm-build |
ca8475 |
if (dead < sizeof(rec))
|
|
rpm-build |
ca8475 |
goto corrupt;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Dead space at %u-%u (of %u)\n",
|
|
rpm-build |
ca8475 |
off, off + dead, tdb->map_size));
|
|
rpm-build |
ca8475 |
rec.rec_len = dead - sizeof(rec);
|
|
rpm-build |
ca8475 |
break;
|
|
rpm-build |
ca8475 |
case TDB_RECOVERY_MAGIC:
|
|
rpm-build |
ca8475 |
if (recovery_start != off) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Unexpected recovery record at offset %u\n",
|
|
rpm-build |
ca8475 |
off));
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
found_recovery = true;
|
|
rpm-build |
ca8475 |
break;
|
|
rpm-build |
ca8475 |
default: ;
|
|
rpm-build |
ca8475 |
corrupt:
|
|
rpm-build |
ca8475 |
tdb->ecode = TDB_ERR_CORRUPT;
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Bad magic 0x%x at offset %u\n",
|
|
rpm-build |
ca8475 |
rec.magic, off));
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* Now, hashes should all be empty: each record exists and is referred
|
|
rpm-build |
ca8475 |
* to by one other. */
|
|
rpm-build |
ca8475 |
for (h = 0; h < 1+tdb->hash_size; h++) {
|
|
rpm-build |
ca8475 |
unsigned int i;
|
|
rpm-build |
ca8475 |
for (i = 0; i < BITMAP_BITS / CHAR_BIT; i++) {
|
|
rpm-build |
ca8475 |
if (hashes[h][i] != 0) {
|
|
rpm-build |
ca8475 |
tdb->ecode = TDB_ERR_CORRUPT;
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Hashes do not match records\n"));
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
/* We must have found recovery area if there was one. */
|
|
rpm-build |
ca8475 |
if (recovery_start != 0 && !found_recovery) {
|
|
rpm-build |
ca8475 |
TDB_LOG((tdb, TDB_DEBUG_ERROR,
|
|
rpm-build |
ca8475 |
"Expected a recovery area at %u\n",
|
|
rpm-build |
ca8475 |
recovery_start));
|
|
rpm-build |
ca8475 |
goto free;
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
free(hashes);
|
|
rpm-build |
ca8475 |
if (locked) {
|
|
rpm-build |
ca8475 |
tdb_unlockall_read(tdb);
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
return 0;
|
|
rpm-build |
ca8475 |
|
|
rpm-build |
ca8475 |
free:
|
|
rpm-build |
ca8475 |
free(hashes);
|
|
rpm-build |
ca8475 |
unlock:
|
|
rpm-build |
ca8475 |
if (locked) {
|
|
rpm-build |
ca8475 |
tdb_unlockall_read(tdb);
|
|
rpm-build |
ca8475 |
}
|
|
rpm-build |
ca8475 |
return -1;
|
|
rpm-build |
ca8475 |
}
|