tdb2: import TDB1 code.
[ccan] / ccan / tdb2 / tdb1_freelist.c
1  /*
2    Unix SMB/CIFS implementation.
3
4    trivial database library
5
6    Copyright (C) Andrew Tridgell              1999-2005
7    Copyright (C) Paul `Rusty' Russell              2000
8    Copyright (C) Jeremy Allison                    2000-2003
9
10      ** NOTE! The following LGPL license applies to the tdb
11      ** library. This does NOT imply that all of Samba is released
12      ** under the LGPL
13
14    This library is free software; you can redistribute it and/or
15    modify it under the terms of the GNU Lesser General Public
16    License as published by the Free Software Foundation; either
17    version 3 of the License, or (at your option) any later version.
18
19    This library is distributed in the hope that it will be useful,
20    but WITHOUT ANY WARRANTY; without even the implied warranty of
21    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
22    Lesser General Public License for more details.
23
24    You should have received a copy of the GNU Lesser General Public
25    License along with this library; if not, see <http://www.gnu.org/licenses/>.
26 */
27
28 #include "tdb1_private.h"
29
30 /* 'right' merges can involve O(n^2) cost when combined with a
31    traverse, so they are disabled until we find a way to do them in
32    O(1) time
33 */
34 #define USE_RIGHT_MERGES 0
35
36 /* read a freelist record and check for simple errors */
37 int tdb1_rec_free_read(struct tdb1_context *tdb, tdb1_off_t off, struct tdb1_record *rec)
38 {
39         if (tdb->methods->tdb1_read(tdb, off, rec, sizeof(*rec),TDB1_DOCONV()) == -1)
40                 return -1;
41
42         if (rec->magic == TDB1_MAGIC) {
43                 /* this happens when a app is showdown while deleting a record - we should
44                    not completely fail when this happens */
45                 TDB1_LOG((tdb, TDB1_DEBUG_WARNING, "tdb1_rec_free_read non-free magic 0x%x at offset=%d - fixing\n",
46                          rec->magic, off));
47                 rec->magic = TDB1_FREE_MAGIC;
48                 if (tdb->methods->tdb1_write(tdb, off, rec, sizeof(*rec)) == -1)
49                         return -1;
50         }
51
52         if (rec->magic != TDB1_FREE_MAGIC) {
53                 /* Ensure ecode is set for log fn. */
54                 tdb->ecode = TDB1_ERR_CORRUPT;
55                 TDB1_LOG((tdb, TDB1_DEBUG_WARNING, "tdb1_rec_free_read bad magic 0x%x at offset=%d\n",
56                            rec->magic, off));
57                 return -1;
58         }
59         if (tdb->methods->tdb1_oob(tdb, rec->next+sizeof(*rec), 0) != 0)
60                 return -1;
61         return 0;
62 }
63
64
65 #if USE_RIGHT_MERGES
66 /* Remove an element from the freelist.  Must have alloc lock. */
67 static int remove_from_freelist(struct tdb1_context *tdb, tdb1_off_t off, tdb1_off_t next)
68 {
69         tdb1_off_t last_ptr, i;
70
71         /* read in the freelist top */
72         last_ptr = TDB1_FREELIST_TOP;
73         while (tdb1_ofs_read(tdb, last_ptr, &i) != -1 && i != 0) {
74                 if (i == off) {
75                         /* We've found it! */
76                         return tdb1_ofs_write(tdb, last_ptr, &next);
77                 }
78                 /* Follow chain (next offset is at start of record) */
79                 last_ptr = i;
80         }
81         tdb->ecode = TDB1_ERR_CORRUPT;
82         TDB1_LOG((tdb, TDB1_DEBUG_FATAL,"remove_from_freelist: not on list at off=%d\n", off));
83         return -1;
84 }
85 #endif
86
87
88 /* update a record tailer (must hold allocation lock) */
89 static int update_tailer(struct tdb1_context *tdb, tdb1_off_t offset,
90                          const struct tdb1_record *rec)
91 {
92         tdb1_off_t totalsize;
93
94         /* Offset of tailer from record header */
95         totalsize = sizeof(*rec) + rec->rec_len;
96         return tdb1_ofs_write(tdb, offset + totalsize - sizeof(tdb1_off_t),
97                          &totalsize);
98 }
99
100 /* Add an element into the freelist. Merge adjacent records if
101    necessary. */
102 int tdb1_free(struct tdb1_context *tdb, tdb1_off_t offset, struct tdb1_record *rec)
103 {
104         /* Allocation and tailer lock */
105         if (tdb1_lock(tdb, -1, F_WRLCK) != 0)
106                 return -1;
107
108         /* set an initial tailer, so if we fail we don't leave a bogus record */
109         if (update_tailer(tdb, offset, rec) != 0) {
110                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: update_tailer failed!\n"));
111                 goto fail;
112         }
113
114 #if USE_RIGHT_MERGES
115         /* Look right first (I'm an Australian, dammit) */
116         if (offset + sizeof(*rec) + rec->rec_len + sizeof(*rec) <= tdb->map_size) {
117                 tdb1_off_t right = offset + sizeof(*rec) + rec->rec_len;
118                 struct tdb1_record r;
119
120                 if (tdb->methods->tdb1_read(tdb, right, &r, sizeof(r), TDB1_DOCONV()) == -1) {
121                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: right read failed at %u\n", right));
122                         goto left;
123                 }
124
125                 /* If it's free, expand to include it. */
126                 if (r.magic == TDB1_FREE_MAGIC) {
127                         if (remove_from_freelist(tdb, right, r.next) == -1) {
128                                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: right free failed at %u\n", right));
129                                 goto left;
130                         }
131                         rec->rec_len += sizeof(r) + r.rec_len;
132                         if (update_tailer(tdb, offset, rec) == -1) {
133                                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: update_tailer failed at %u\n", offset));
134                                 goto fail;
135                         }
136                 }
137         }
138 left:
139 #endif
140
141         /* Look left */
142         if (offset - sizeof(tdb1_off_t) > TDB1_DATA_START(tdb->header.hash_size)) {
143                 tdb1_off_t left = offset - sizeof(tdb1_off_t);
144                 struct tdb1_record l;
145                 tdb1_off_t leftsize;
146
147                 /* Read in tailer and jump back to header */
148                 if (tdb1_ofs_read(tdb, left, &leftsize) == -1) {
149                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: left offset read failed at %u\n", left));
150                         goto update;
151                 }
152
153                 /* it could be uninitialised data */
154                 if (leftsize == 0 || leftsize == TDB1_PAD_U32) {
155                         goto update;
156                 }
157
158                 left = offset - leftsize;
159
160                 if (leftsize > offset ||
161                     left < TDB1_DATA_START(tdb->header.hash_size)) {
162                         goto update;
163                 }
164
165                 /* Now read in the left record */
166                 if (tdb->methods->tdb1_read(tdb, left, &l, sizeof(l), TDB1_DOCONV()) == -1) {
167                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: left read failed at %u (%u)\n", left, leftsize));
168                         goto update;
169                 }
170
171                 /* If it's free, expand to include it. */
172                 if (l.magic == TDB1_FREE_MAGIC) {
173                         /* we now merge the new record into the left record, rather than the other
174                            way around. This makes the operation O(1) instead of O(n). This change
175                            prevents traverse from being O(n^2) after a lot of deletes */
176                         l.rec_len += sizeof(*rec) + rec->rec_len;
177                         if (tdb1_rec_write(tdb, left, &l) == -1) {
178                                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: update_left failed at %u\n", left));
179                                 goto fail;
180                         }
181                         if (update_tailer(tdb, left, &l) == -1) {
182                                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free: update_tailer failed at %u\n", offset));
183                                 goto fail;
184                         }
185                         tdb1_unlock(tdb, -1, F_WRLCK);
186                         return 0;
187                 }
188         }
189
190 update:
191
192         /* Now, prepend to free list */
193         rec->magic = TDB1_FREE_MAGIC;
194
195         if (tdb1_ofs_read(tdb, TDB1_FREELIST_TOP, &rec->next) == -1 ||
196             tdb1_rec_write(tdb, offset, rec) == -1 ||
197             tdb1_ofs_write(tdb, TDB1_FREELIST_TOP, &offset) == -1) {
198                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_free record write failed at offset=%d\n", offset));
199                 goto fail;
200         }
201
202         /* And we're done. */
203         tdb1_unlock(tdb, -1, F_WRLCK);
204         return 0;
205
206  fail:
207         tdb1_unlock(tdb, -1, F_WRLCK);
208         return -1;
209 }
210
211
212
213 /*
214    the core of tdb1_allocate - called when we have decided which
215    free list entry to use
216
217    Note that we try to allocate by grabbing data from the end of an existing record,
218    not the beginning. This is so the left merge in a free is more likely to be
219    able to free up the record without fragmentation
220  */
221 static tdb1_off_t tdb1_allocate_ofs(struct tdb1_context *tdb,
222                                   tdb1_len_t length, tdb1_off_t rec_ptr,
223                                   struct tdb1_record *rec, tdb1_off_t last_ptr)
224 {
225 #define MIN_REC_SIZE (sizeof(struct tdb1_record) + sizeof(tdb1_off_t) + 8)
226
227         if (rec->rec_len < length + MIN_REC_SIZE) {
228                 /* we have to grab the whole record */
229
230                 /* unlink it from the previous record */
231                 if (tdb1_ofs_write(tdb, last_ptr, &rec->next) == -1) {
232                         return 0;
233                 }
234
235                 /* mark it not free */
236                 rec->magic = TDB1_MAGIC;
237                 if (tdb1_rec_write(tdb, rec_ptr, rec) == -1) {
238                         return 0;
239                 }
240                 return rec_ptr;
241         }
242
243         /* we're going to just shorten the existing record */
244         rec->rec_len -= (length + sizeof(*rec));
245         if (tdb1_rec_write(tdb, rec_ptr, rec) == -1) {
246                 return 0;
247         }
248         if (update_tailer(tdb, rec_ptr, rec) == -1) {
249                 return 0;
250         }
251
252         /* and setup the new record */
253         rec_ptr += sizeof(*rec) + rec->rec_len;
254
255         memset(rec, '\0', sizeof(*rec));
256         rec->rec_len = length;
257         rec->magic = TDB1_MAGIC;
258
259         if (tdb1_rec_write(tdb, rec_ptr, rec) == -1) {
260                 return 0;
261         }
262
263         if (update_tailer(tdb, rec_ptr, rec) == -1) {
264                 return 0;
265         }
266
267         return rec_ptr;
268 }
269
270 /* allocate some space from the free list. The offset returned points
271    to a unconnected tdb1_record within the database with room for at
272    least length bytes of total data
273
274    0 is returned if the space could not be allocated
275  */
276 tdb1_off_t tdb1_allocate(struct tdb1_context *tdb, tdb1_len_t length, struct tdb1_record *rec)
277 {
278         tdb1_off_t rec_ptr, last_ptr, newrec_ptr;
279         struct {
280                 tdb1_off_t rec_ptr, last_ptr;
281                 tdb1_len_t rec_len;
282         } bestfit;
283         float multiplier = 1.0;
284
285         if (tdb1_lock(tdb, -1, F_WRLCK) == -1)
286                 return 0;
287
288         /* over-allocate to reduce fragmentation */
289         length *= 1.25;
290
291         /* Extra bytes required for tailer */
292         length += sizeof(tdb1_off_t);
293         length = TDB1_ALIGN(length, TDB1_ALIGNMENT);
294
295  again:
296         last_ptr = TDB1_FREELIST_TOP;
297
298         /* read in the freelist top */
299         if (tdb1_ofs_read(tdb, TDB1_FREELIST_TOP, &rec_ptr) == -1)
300                 goto fail;
301
302         bestfit.rec_ptr = 0;
303         bestfit.last_ptr = 0;
304         bestfit.rec_len = 0;
305
306         /*
307            this is a best fit allocation strategy. Originally we used
308            a first fit strategy, but it suffered from massive fragmentation
309            issues when faced with a slowly increasing record size.
310          */
311         while (rec_ptr) {
312                 if (tdb1_rec_free_read(tdb, rec_ptr, rec) == -1) {
313                         goto fail;
314                 }
315
316                 if (rec->rec_len >= length) {
317                         if (bestfit.rec_ptr == 0 ||
318                             rec->rec_len < bestfit.rec_len) {
319                                 bestfit.rec_len = rec->rec_len;
320                                 bestfit.rec_ptr = rec_ptr;
321                                 bestfit.last_ptr = last_ptr;
322                         }
323                 }
324
325                 /* move to the next record */
326                 last_ptr = rec_ptr;
327                 rec_ptr = rec->next;
328
329                 /* if we've found a record that is big enough, then
330                    stop searching if its also not too big. The
331                    definition of 'too big' changes as we scan
332                    through */
333                 if (bestfit.rec_len > 0 &&
334                     bestfit.rec_len < length * multiplier) {
335                         break;
336                 }
337
338                 /* this multiplier means we only extremely rarely
339                    search more than 50 or so records. At 50 records we
340                    accept records up to 11 times larger than what we
341                    want */
342                 multiplier *= 1.05;
343         }
344
345         if (bestfit.rec_ptr != 0) {
346                 if (tdb1_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
347                         goto fail;
348                 }
349
350                 newrec_ptr = tdb1_allocate_ofs(tdb, length, bestfit.rec_ptr,
351                                               rec, bestfit.last_ptr);
352                 tdb1_unlock(tdb, -1, F_WRLCK);
353                 return newrec_ptr;
354         }
355
356         /* we didn't find enough space. See if we can expand the
357            database and if we can then try again */
358         if (tdb1_expand(tdb, length + sizeof(*rec)) == 0)
359                 goto again;
360  fail:
361         tdb1_unlock(tdb, -1, F_WRLCK);
362         return 0;
363 }
364
365
366
367 /*
368    return the size of the freelist - used to decide if we should repack
369 */
370 _PUBLIC_ int tdb1_freelist_size(struct tdb1_context *tdb)
371 {
372         tdb1_off_t ptr;
373         int count=0;
374
375         if (tdb1_lock(tdb, -1, F_RDLCK) == -1) {
376                 return -1;
377         }
378
379         ptr = TDB1_FREELIST_TOP;
380         while (tdb1_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) {
381                 count++;
382         }
383
384         tdb1_unlock(tdb, -1, F_RDLCK);
385         return count;
386 }