summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichael Adam <obnox@samba.org>2014-06-11 12:05:57 +0200
committerVolker Lendecke <vl@samba.org>2014-06-26 12:16:03 +0200
commit55ff3a3b912a911cb33b47f55be2966fbbbde2d8 (patch)
treeef1113d0f8c0d80379af00c5a11c35107165aa97
parent6502df58391cc8d3477d1c5cce4a6aa027d439bd (diff)
downloadsamba-55ff3a3b912a911cb33b47f55be2966fbbbde2d8.tar.gz
samba-55ff3a3b912a911cb33b47f55be2966fbbbde2d8.tar.xz
samba-55ff3a3b912a911cb33b47f55be2966fbbbde2d8.zip
tdb: defragment the freelist in tdb_allocate_from_freelist()
While we are traversing the freelist anyways, merge a record with the left if it is also a free list record. That partially makes up for the fragmentation introduced by the lack of merging with right records in tdb_free(). Note there is a potential slight downside: If the left record we merge the current record into was earlier in the chain and has hence already been met in traverse, then we can not use the enlarged record even if it might be a new best fit. Signed-off-by: Michael Adam <obnox@samba.org> Reviewed-by: Volker Lendecke <vl@samba.org> Autobuild-User(master): Volker Lendecke <vl@samba.org> Autobuild-Date(master): Thu Jun 26 12:16:03 CEST 2014 on sn-devel-104
-rw-r--r--lib/tdb/common/freelist.c55
1 files changed, 55 insertions, 0 deletions
diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
index 18b5bf1b67..86fac2ff07 100644
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -449,6 +449,7 @@ static tdb_off_t tdb_allocate_from_freelist(
tdb_len_t rec_len;
} bestfit;
float multiplier = 1.0;
+ bool merge_created_candidate;
/* over-allocate to reduce fragmentation */
length *= 1.25;
@@ -458,6 +459,7 @@ static tdb_off_t tdb_allocate_from_freelist(
length = TDB_ALIGN(length, TDB_ALIGNMENT);
again:
+ merge_created_candidate = false;
last_ptr = FREELIST_TOP;
/* read in the freelist top */
@@ -474,10 +476,59 @@ static tdb_off_t tdb_allocate_from_freelist(
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) {
@@ -517,6 +568,10 @@ static tdb_off_t tdb_allocate_from_freelist(
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)