return 0;
}
-/* Add an element into the freelist. Merge adjacent records if
- necessary. */
+/**
+ * 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)
{
- tdb_off_t left;
- struct tdb_record l;
+ int ret;
/* Allocation and tailer lock */
if (tdb_lock(tdb, -1, F_WRLCK) != 0)
left:
#endif
- if (read_record_on_left(tdb, offset, &left, &l) != 0) {
- goto update;
- }
-
- if (l.magic != TDB_FREE_MAGIC) {
- goto update;
- }
-
- /* It's free - expand to include it. */
-
- /* 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));
+ ret = check_merge_with_left_record(tdb, offset, rec, NULL, NULL);
+ if (ret == -1) {
goto fail;
}
- if (update_tailer(tdb, left, &l) == -1) {
- TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", left));
- goto fail;
+ if (ret == 1) {
+ /* merged */
+ goto done;
}
- tdb_unlock(tdb, -1, F_WRLCK);
- return 0;
-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;
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 / metze / samba / wip.git / blobdiff