&totalsize);
}
-/* Add an element into the freelist. Merge adjacent records if
- necessary. */
+/**
+ * Read the record directly on the left.
+ * Fail if there is no record on the left.
+ */
+static int read_record_on_left(struct tdb_context *tdb, tdb_off_t rec_ptr,
+ tdb_off_t *left_p,
+ struct tdb_record *left_r)
+{
+ tdb_off_t left_ptr;
+ tdb_off_t left_size;
+ struct tdb_record left_rec;
+ int ret;
+
+ left_ptr = rec_ptr - sizeof(tdb_off_t);
+
+ if (left_ptr <= TDB_DATA_START(tdb->hash_size)) {
+ /* no record on the left */
+ return -1;
+ }
+
+ /* Read in tailer and jump back to header */
+ ret = tdb_ofs_read(tdb, left_ptr, &left_size);
+ if (ret == -1) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL,
+ "tdb_free: left offset read failed at %u\n", left_ptr));
+ return -1;
+ }
+
+ /* it could be uninitialised data */
+ if (left_size == 0 || left_size == TDB_PAD_U32) {
+ return -1;
+ }
+
+ if (left_size > rec_ptr) {
+ return -1;
+ }
+
+ left_ptr = rec_ptr - left_size;
+
+ if (left_ptr < TDB_DATA_START(tdb->hash_size)) {
+ return -1;
+ }
+
+ /* Now read in the left record */
+ ret = tdb->methods->tdb_read(tdb, left_ptr, &left_rec,
+ sizeof(left_rec), DOCONV());
+ if (ret == -1) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL,
+ "tdb_free: left read failed at %u (%u)\n",
+ left_ptr, left_size));
+ return -1;
+ }
+
+ *left_p = left_ptr;
+ *left_r = left_rec;
+
+ return 0;
+}
+
+/**
+ * Merge new freelist record with the direct left neighbour.
+ * This assumes that left_rec represents the record
+ * directly to the left of right_rec and that this is
+ * a freelist record.
+ */
+static int merge_with_left_record(struct tdb_context *tdb,
+ tdb_off_t left_ptr,
+ struct tdb_record *left_rec,
+ struct tdb_record *right_rec)
+{
+ int ret;
+
+ left_rec->rec_len += sizeof(*right_rec) + right_rec->rec_len;
+
+ ret = tdb_rec_write(tdb, left_ptr, left_rec);
+ if (ret == -1) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL,
+ "merge_with_left_record: update_left failed at %u\n",
+ left_ptr));
+ return -1;
+ }
+
+ ret = update_tailer(tdb, left_ptr, left_rec);
+ if (ret == -1) {
+ TDB_LOG((tdb, TDB_DEBUG_FATAL,
+ "merge_with_left_record: update_tailer failed at %u\n",
+ left_ptr));
+ return -1;
+ }
+
+ return 0;
+}
+
+/**
+ * Check whether the record left of a given freelist record is
+ * also a freelist record, and if so, merge the two records.
+ *
+ * Return code:
+ * -1 upon error
+ * 0 if left was not a free record
+ * 1 if left was free and successfully merged.
+ *
+ * The currend record is handed in with pointer and fully read record.
+ *
+ * The left record pointer and struct can be retrieved as result
+ * in lp and lr;
+ */
+static int check_merge_with_left_record(struct tdb_context *tdb,
+ tdb_off_t rec_ptr,
+ struct tdb_record *rec,
+ tdb_off_t *lp,
+ struct tdb_record *lr)
+{
+ tdb_off_t left_ptr;
+ struct tdb_record left_rec;
+ int ret;
+
+ ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
+ if (ret != 0) {
+ return 0;
+ }
+
+ if (left_rec.magic != TDB_FREE_MAGIC) {
+ return 0;
+ }
+
+ /* It's free - expand to include it. */
+ ret = merge_with_left_record(tdb, left_ptr, &left_rec, rec);
+ if (ret != 0) {
+ return -1;
+ }
+
+ if (lp != NULL) {
+ *lp = left_ptr;
+ }
+
+ if (lr != NULL) {
+ *lr = left_rec;
+ }
+
+ return 1;
+}
+
+/**
+ * Check whether the record left of a given freelist record is
+ * also a freelist record, and if so, merge the two records.
+ *
+ * Return code:
+ * -1 upon error
+ * 0 if left was not a free record
+ * 1 if left was free and successfully merged.
+ *
+ * In this variant, the input record is specified just as the pointer
+ * and is read from the database if needed.
+ *
+ * next_ptr will contain the original record's next pointer after
+ * successful merging (which will be lost after merging), so that
+ * the caller can update the last pointer.
+ */
+static int check_merge_ptr_with_left_record(struct tdb_context *tdb,
+ tdb_off_t rec_ptr,
+ tdb_off_t *next_ptr)
+{
+ tdb_off_t left_ptr;
+ struct tdb_record rec, left_rec;
+ int ret;
+
+ ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
+ if (ret != 0) {
+ return 0;
+ }
+
+ if (left_rec.magic != TDB_FREE_MAGIC) {
+ return 0;
+ }
+
+ /* It's free - expand to include it. */
+
+ ret = tdb->methods->tdb_read(tdb, rec_ptr, &rec,
+ sizeof(rec), DOCONV());
+ if (ret != 0) {
+ return -1;
+ }
+
+ ret = merge_with_left_record(tdb, left_ptr, &left_rec, &rec);
+ if (ret != 0) {
+ return -1;
+ }
+
+ if (next_ptr != NULL) {
+ *next_ptr = rec.next;
+ }
+
+ return 1;
+}
+
+/**
+ * Add an element into the freelist.
+ *
+ * We merge the new record into the left record if it is also a
+ * free record, but not with the right one. This makes the
+ * operation O(1) instead of O(n): merging with the right record
+ * requires a traverse of the freelist to find the previous
+ * record in the free list.
+ *
+ * This prevents db traverses from being O(n^2) after a lot of deletes.
+ */
int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
{
+ int ret;
+
/* Allocation and tailer lock */
if (tdb_lock(tdb, -1, F_WRLCK) != 0)
return -1;
left:
#endif
- /* Look left */
- if (offset - sizeof(tdb_off_t) > TDB_DATA_START(tdb->hash_size)) {
- tdb_off_t left = offset - sizeof(tdb_off_t);
- struct tdb_record l;
- tdb_off_t leftsize;
-
- /* Read in tailer and jump back to header */
- if (tdb_ofs_read(tdb, left, &leftsize) == -1) {
- TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left offset read failed at %u\n", left));
- goto update;
- }
-
- /* it could be uninitialised data */
- if (leftsize == 0 || leftsize == TDB_PAD_U32) {
- goto update;
- }
-
- left = offset - leftsize;
-
- if (leftsize > offset ||
- left < TDB_DATA_START(tdb->hash_size)) {
- goto update;
- }
-
- /* Now read in the left record */
- if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
- TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
- goto update;
- }
-
- /* If it's free, expand to include it. */
- if (l.magic == TDB_FREE_MAGIC) {
- /* we now merge the new record into the left record, rather than the other
- way around. This makes the operation O(1) instead of O(n). This change
- prevents traverse from being O(n^2) after a lot of deletes */
- l.rec_len += sizeof(*rec) + rec->rec_len;
- if (tdb_rec_write(tdb, left, &l) == -1) {
- TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_left failed at %u\n", left));
- goto fail;
- }
- if (update_tailer(tdb, left, &l) == -1) {
- TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
- goto fail;
- }
- tdb_unlock(tdb, -1, F_WRLCK);
- return 0;
- }
+ ret = check_merge_with_left_record(tdb, offset, rec, NULL, NULL);
+ if (ret == -1) {
+ goto fail;
+ }
+ if (ret == 1) {
+ /* merged */
+ goto done;
}
-update:
+ /* Nothing to merge, prepend to free list */
- /* Now, prepend to free list */
rec->magic = TDB_FREE_MAGIC;
if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
goto fail;
}
+done:
/* And we're done. */
tdb_unlock(tdb, -1, F_WRLCK);
return 0;
tdb_len_t rec_len;
} bestfit;
float multiplier = 1.0;
+ bool merge_created_candidate;
/* over-allocate to reduce fragmentation */
length *= 1.25;
length = TDB_ALIGN(length, TDB_ALIGNMENT);
again:
+ merge_created_candidate = false;
last_ptr = FREELIST_TOP;
/* read in the freelist top */
issues when faced with a slowly increasing record size.
*/
while (rec_ptr) {
+ int ret;
+ tdb_off_t left_ptr;
+ struct tdb_record left_rec;
+
if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
return 0;
}
+ ret = check_merge_with_left_record(tdb, rec_ptr, rec,
+ &left_ptr, &left_rec);
+ if (ret == -1) {
+ return 0;
+ }
+ if (ret == 1) {
+ /* merged */
+ rec_ptr = rec->next;
+ ret = tdb_ofs_write(tdb, last_ptr, &rec->next);
+ if (ret == -1) {
+ return 0;
+ }
+
+ /*
+ * We have merged the current record into the left
+ * neighbour. So our traverse of the freelist will
+ * skip it and consider the next record in the chain.
+ *
+ * But the enlarged left neighbour may be a candidate.
+ * If it is, we can not directly use it, though.
+ * The only thing we can do and have to do here is to
+ * update the current best fit size in the chain if the
+ * current best fit is the left record. (By that we may
+ * worsen the best fit we already had, bit this is not a
+ * problem.)
+ *
+ * If the current best fit is not the left record,
+ * all we can do is remember the fact that a merge
+ * created a new candidate so that we can trigger
+ * a second walk of the freelist if at the end of
+ * the first walk we have not found any fit.
+ * This way we can avoid expanding the database.
+ */
+
+ if (bestfit.rec_ptr == left_ptr) {
+ bestfit.rec_len = left_rec.rec_len;
+ }
+
+ if (left_rec.rec_len > length) {
+ merge_created_candidate = true;
+ }
+
+ continue;
+ }
+
if (rec->rec_len >= length) {
if (bestfit.rec_ptr == 0 ||
rec->rec_len < bestfit.rec_len) {
return newrec_ptr;
}
+ if (merge_created_candidate) {
+ goto again;
+ }
+
/* we didn't find enough space. See if we can expand the
database and if we can then try again */
if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
* hash chains, something which is pretty bad normally)
*/
- for (i=1; i<tdb->hash_size; i++) {
+ for (i=0; i<tdb->hash_size; i++) {
int list;
- if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == 0) {
- /*
- * Under the freelist lock take the chance to give
- * back our dead records.
- */
- tdb_purge_dead(tdb, hash);
-
- ret = tdb_allocate_from_freelist(tdb, length, rec);
- tdb_unlock(tdb, -1, F_WRLCK);
- return ret;
- }
-
list = BUCKET(hash+i);
if (tdb_lock_nonblock(tdb, list, F_WRLCK) == 0) {
return ret;
}
}
+
+ if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == 0) {
+ /*
+ * Under the freelist lock take the chance to give
+ * back our dead records.
+ */
+ tdb_purge_dead(tdb, hash);
+
+ ret = tdb_allocate_from_freelist(tdb, length, rec);
+ tdb_unlock(tdb, -1, F_WRLCK);
+ return ret;
+ }
}
blocking_freelist_allocate:
return ret;
}
-/*
- return the size of the freelist - used to decide if we should repack
-*/
-_PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
+/**
+ * Merge adjacent records in the freelist.
+ */
+static int tdb_freelist_merge_adjacent(struct tdb_context *tdb,
+ int *count_records, int *count_merged)
+{
+ tdb_off_t cur, next;
+ int count = 0;
+ int merged = 0;
+ int ret;
+
+ ret = tdb_lock(tdb, -1, F_RDLCK);
+ if (ret == -1) {
+ return -1;
+ }
+
+ cur = FREELIST_TOP;
+ while (tdb_ofs_read(tdb, cur, &next) == 0 && next != 0) {
+ tdb_off_t next2;
+
+ count++;
+
+ ret = check_merge_ptr_with_left_record(tdb, next, &next2);
+ if (ret == -1) {
+ goto done;
+ }
+ if (ret == 1) {
+ /*
+ * merged:
+ * now let cur->next point to next2 instead of next
+ */
+
+ ret = tdb_ofs_write(tdb, cur, &next2);
+ if (ret != 0) {
+ goto done;
+ }
+
+ next = next2;
+ merged++;
+ }
+
+ cur = next;
+ }
+
+ if (count_records != NULL) {
+ *count_records = count;
+ }
+
+ if (count_merged != NULL) {
+ *count_merged = merged;
+ }
+
+ ret = 0;
+
+done:
+ tdb_unlock(tdb, -1, F_RDLCK);
+ return ret;
+}
+
+/**
+ * return the size of the freelist - no merging done
+ */
+static int tdb_freelist_size_no_merge(struct tdb_context *tdb)
{
tdb_off_t ptr;
int count=0;
tdb_unlock(tdb, -1, F_RDLCK);
return count;
}
+
+/**
+ * return the size of the freelist - used to decide if we should repack
+ *
+ * As a side effect, adjacent records are merged unless the
+ * database is read-only, in order to reduce the fragmentation
+ * without repacking.
+ */
+_PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
+{
+
+ int count = 0;
+
+ if (tdb->read_only) {
+ count = tdb_freelist_size_no_merge(tdb);
+ } else {
+ int ret;
+ ret = tdb_freelist_merge_adjacent(tdb, &count, NULL);
+ if (ret != 0) {
+ return -1;
+ }
+ }
+
+ return count;
+}
git.samba.org / samba.git / blobdiff