vfs_aixacl2: Fix "mem_ctx" and "ppdesc" smb_fget_nt_acl_nfs4 args
[samba.git] / lib / tdb / common / 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 "tdb_private.h"
29
30 /* read a freelist record and check for simple errors */
31 int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct tdb_record *rec)
32 {
33         if (tdb->methods->tdb_read(tdb, off, rec, sizeof(*rec),DOCONV()) == -1)
34                 return -1;
35
36         if (rec->magic == TDB_MAGIC) {
37                 /* this happens when a app is showdown while deleting a record - we should
38                    not completely fail when this happens */
39                 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read non-free magic 0x%x at offset=%u - fixing\n",
40                          rec->magic, off));
41                 rec->magic = TDB_FREE_MAGIC;
42                 if (tdb_rec_write(tdb, off, rec) == -1)
43                         return -1;
44         }
45
46         if (rec->magic != TDB_FREE_MAGIC) {
47                 /* Ensure ecode is set for log fn. */
48                 tdb->ecode = TDB_ERR_CORRUPT;
49                 TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_rec_free_read bad magic 0x%x at offset=%u\n",
50                            rec->magic, off));
51                 return -1;
52         }
53         if (tdb_oob(tdb, rec->next, sizeof(*rec), 0) != 0)
54                 return -1;
55         return 0;
56 }
57
58 /* update a record tailer (must hold allocation lock) */
59 static int update_tailer(struct tdb_context *tdb, tdb_off_t offset,
60                          const struct tdb_record *rec)
61 {
62         tdb_off_t totalsize;
63
64         /* Offset of tailer from record header */
65         totalsize = sizeof(*rec) + rec->rec_len;
66         return tdb_ofs_write(tdb, offset + totalsize - sizeof(tdb_off_t),
67                          &totalsize);
68 }
69
70 /**
71  * Read the record directly on the left.
72  * Fail if there is no record on the left.
73  */
74 static int read_record_on_left(struct tdb_context *tdb, tdb_off_t rec_ptr,
75                                tdb_off_t *left_p,
76                                struct tdb_record *left_r)
77 {
78         tdb_off_t left_ptr;
79         tdb_off_t left_size;
80         struct tdb_record left_rec;
81         int ret;
82
83         left_ptr = rec_ptr - sizeof(tdb_off_t);
84
85         if (left_ptr <= TDB_DATA_START(tdb->hash_size)) {
86                 /* no record on the left */
87                 return -1;
88         }
89
90         /* Read in tailer and jump back to header */
91         ret = tdb_ofs_read(tdb, left_ptr, &left_size);
92         if (ret == -1) {
93                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
94                         "tdb_free: left offset read failed at %u\n", left_ptr));
95                 return -1;
96         }
97
98         /* it could be uninitialised data */
99         if (left_size == 0 || left_size == TDB_PAD_U32) {
100                 return -1;
101         }
102
103         if (left_size > rec_ptr) {
104                 return -1;
105         }
106
107         left_ptr = rec_ptr - left_size;
108
109         if (left_ptr < TDB_DATA_START(tdb->hash_size)) {
110                 return -1;
111         }
112
113         /* Now read in the left record */
114         ret = tdb->methods->tdb_read(tdb, left_ptr, &left_rec,
115                                      sizeof(left_rec), DOCONV());
116         if (ret == -1) {
117                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
118                          "tdb_free: left read failed at %u (%u)\n",
119                          left_ptr, left_size));
120                 return -1;
121         }
122
123         *left_p = left_ptr;
124         *left_r = left_rec;
125
126         return 0;
127 }
128
129 /**
130  * Merge new freelist record with the direct left neighbour.
131  * This assumes that left_rec represents the record
132  * directly to the left of right_rec and that this is
133  * a freelist record.
134  */
135 static int merge_with_left_record(struct tdb_context *tdb,
136                                   tdb_off_t left_ptr,
137                                   struct tdb_record *left_rec,
138                                   struct tdb_record *right_rec)
139 {
140         int ret;
141
142         left_rec->rec_len += sizeof(*right_rec) + right_rec->rec_len;
143
144         ret = tdb_rec_write(tdb, left_ptr, left_rec);
145         if (ret == -1) {
146                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
147                          "merge_with_left_record: update_left failed at %u\n",
148                          left_ptr));
149                 return -1;
150         }
151
152         ret = update_tailer(tdb, left_ptr, left_rec);
153         if (ret == -1) {
154                 TDB_LOG((tdb, TDB_DEBUG_FATAL,
155                          "merge_with_left_record: update_tailer failed at %u\n",
156                          left_ptr));
157                 return -1;
158         }
159
160         return 0;
161 }
162
163 /**
164  * Check whether the record left of a given freelist record is
165  * also a freelist record, and if so, merge the two records.
166  *
167  * Return code:
168  *  -1 upon error
169  *   0 if left was not a free record
170  *   1 if left was free and successfully merged.
171  *
172  * The current record is handed in with pointer and fully read record.
173  *
174  * The left record pointer and struct can be retrieved as result
175  * in lp and lr;
176  */
177 static int check_merge_with_left_record(struct tdb_context *tdb,
178                                         tdb_off_t rec_ptr,
179                                         struct tdb_record *rec,
180                                         tdb_off_t *lp,
181                                         struct tdb_record *lr)
182 {
183         tdb_off_t left_ptr;
184         struct tdb_record left_rec;
185         int ret;
186
187         ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
188         if (ret != 0) {
189                 return 0;
190         }
191
192         if (left_rec.magic != TDB_FREE_MAGIC) {
193                 return 0;
194         }
195
196         /* It's free - expand to include it. */
197         ret = merge_with_left_record(tdb, left_ptr, &left_rec, rec);
198         if (ret != 0) {
199                 return -1;
200         }
201
202         if (lp != NULL) {
203                 *lp = left_ptr;
204         }
205
206         if (lr != NULL) {
207                 *lr = left_rec;
208         }
209
210         return 1;
211 }
212
213 /**
214  * Check whether the record left of a given freelist record is
215  * also a freelist record, and if so, merge the two records.
216  *
217  * Return code:
218  *  -1 upon error
219  *   0 if left was not a free record
220  *   1 if left was free and successfully merged.
221  *
222  * In this variant, the input record is specified just as the pointer
223  * and is read from the database if needed.
224  *
225  * next_ptr will contain the original record's next pointer after
226  * successful merging (which will be lost after merging), so that
227  * the caller can update the last pointer.
228  */
229 static int check_merge_ptr_with_left_record(struct tdb_context *tdb,
230                                             tdb_off_t rec_ptr,
231                                             tdb_off_t *next_ptr)
232 {
233         tdb_off_t left_ptr;
234         struct tdb_record rec, left_rec;
235         int ret;
236
237         ret = read_record_on_left(tdb, rec_ptr, &left_ptr, &left_rec);
238         if (ret != 0) {
239                 return 0;
240         }
241
242         if (left_rec.magic != TDB_FREE_MAGIC) {
243                 return 0;
244         }
245
246         /* It's free - expand to include it. */
247
248         ret = tdb->methods->tdb_read(tdb, rec_ptr, &rec,
249                                      sizeof(rec), DOCONV());
250         if (ret != 0) {
251                 return -1;
252         }
253
254         ret = merge_with_left_record(tdb, left_ptr, &left_rec, &rec);
255         if (ret != 0) {
256                 return -1;
257         }
258
259         if (next_ptr != NULL) {
260                 *next_ptr = rec.next;
261         }
262
263         return 1;
264 }
265
266 /**
267  * Add an element into the freelist.
268  *
269  * We merge the new record into the left record if it is also a
270  * free record, but not with the right one. This makes the
271  * operation O(1) instead of O(n): merging with the right record
272  * requires a traverse of the freelist to find the previous
273  * record in the free list.
274  *
275  * This prevents db traverses from being O(n^2) after a lot of deletes.
276  */
277 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec)
278 {
279         int ret;
280
281         /* Allocation and tailer lock */
282         if (tdb_lock(tdb, -1, F_WRLCK) != 0)
283                 return -1;
284
285         /* set an initial tailer, so if we fail we don't leave a bogus record */
286         if (update_tailer(tdb, offset, rec) != 0) {
287                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed!\n"));
288                 goto fail;
289         }
290
291         ret = check_merge_with_left_record(tdb, offset, rec, NULL, NULL);
292         if (ret == -1) {
293                 goto fail;
294         }
295         if (ret == 1) {
296                 /* merged */
297                 goto done;
298         }
299
300         /* Nothing to merge, prepend to free list */
301
302         rec->magic = TDB_FREE_MAGIC;
303
304         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec->next) == -1 ||
305             tdb_rec_write(tdb, offset, rec) == -1 ||
306             tdb_ofs_write(tdb, FREELIST_TOP, &offset) == -1) {
307                 TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free record write failed at offset=%u\n", offset));
308                 goto fail;
309         }
310
311 done:
312         /* And we're done. */
313         tdb_unlock(tdb, -1, F_WRLCK);
314         return 0;
315
316  fail:
317         tdb_unlock(tdb, -1, F_WRLCK);
318         return -1;
319 }
320
321
322
323 /*
324    the core of tdb_allocate - called when we have decided which
325    free list entry to use
326
327    Note that we try to allocate by grabbing data from the end of an existing record,
328    not the beginning. This is so the left merge in a free is more likely to be
329    able to free up the record without fragmentation
330  */
331 static tdb_off_t tdb_allocate_ofs(struct tdb_context *tdb,
332                                   tdb_len_t length, tdb_off_t rec_ptr,
333                                   struct tdb_record *rec, tdb_off_t last_ptr)
334 {
335 #define MIN_REC_SIZE (sizeof(struct tdb_record) + sizeof(tdb_off_t) + 8)
336
337         if (rec->rec_len < length + MIN_REC_SIZE) {
338                 /* we have to grab the whole record */
339
340                 /* unlink it from the previous record */
341                 if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1) {
342                         return 0;
343                 }
344
345                 /* mark it not free */
346                 rec->magic = TDB_MAGIC;
347                 if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
348                         return 0;
349                 }
350                 return rec_ptr;
351         }
352
353         /* we're going to just shorten the existing record */
354         rec->rec_len -= (length + sizeof(*rec));
355         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
356                 return 0;
357         }
358         if (update_tailer(tdb, rec_ptr, rec) == -1) {
359                 return 0;
360         }
361
362         /* and setup the new record */
363         rec_ptr += sizeof(*rec) + rec->rec_len;
364
365         memset(rec, '\0', sizeof(*rec));
366         rec->rec_len = length;
367         rec->magic = TDB_MAGIC;
368
369         if (tdb_rec_write(tdb, rec_ptr, rec) == -1) {
370                 return 0;
371         }
372
373         if (update_tailer(tdb, rec_ptr, rec) == -1) {
374                 return 0;
375         }
376
377         return rec_ptr;
378 }
379
380 /* allocate some space from the free list. The offset returned points
381    to a unconnected tdb_record within the database with room for at
382    least length bytes of total data
383
384    0 is returned if the space could not be allocated
385  */
386 static tdb_off_t tdb_allocate_from_freelist(
387         struct tdb_context *tdb, tdb_len_t length, struct tdb_record *rec)
388 {
389         tdb_off_t rec_ptr, last_ptr, newrec_ptr;
390         struct tdb_chainwalk_ctx chainwalk;
391         bool modified;
392         struct {
393                 tdb_off_t rec_ptr, last_ptr;
394                 tdb_len_t rec_len;
395         } bestfit;
396         float multiplier = 1.0;
397         bool merge_created_candidate;
398
399         /* over-allocate to reduce fragmentation */
400         length *= 1.25;
401
402         /* Extra bytes required for tailer */
403         length += sizeof(tdb_off_t);
404         length = TDB_ALIGN(length, TDB_ALIGNMENT);
405
406  again:
407         merge_created_candidate = false;
408         last_ptr = FREELIST_TOP;
409
410         /* read in the freelist top */
411         if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
412                 return 0;
413
414         modified = false;
415         tdb_chainwalk_init(&chainwalk, rec_ptr);
416
417         bestfit.rec_ptr = 0;
418         bestfit.last_ptr = 0;
419         bestfit.rec_len = 0;
420
421         /*
422            this is a best fit allocation strategy. Originally we used
423            a first fit strategy, but it suffered from massive fragmentation
424            issues when faced with a slowly increasing record size.
425          */
426         while (rec_ptr) {
427                 int ret;
428                 tdb_off_t left_ptr;
429                 struct tdb_record left_rec;
430
431                 if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
432                         return 0;
433                 }
434
435                 ret = check_merge_with_left_record(tdb, rec_ptr, rec,
436                                                    &left_ptr, &left_rec);
437                 if (ret == -1) {
438                         return 0;
439                 }
440                 if (ret == 1) {
441                         /* merged */
442                         rec_ptr = rec->next;
443                         ret = tdb_ofs_write(tdb, last_ptr, &rec->next);
444                         if (ret == -1) {
445                                 return 0;
446                         }
447
448                         /*
449                          * We have merged the current record into the left
450                          * neighbour. So our traverse of the freelist will
451                          * skip it and consider the next record in the chain.
452                          *
453                          * But the enlarged left neighbour may be a candidate.
454                          * If it is, we can not directly use it, though.
455                          * The only thing we can do and have to do here is to
456                          * update the current best fit size in the chain if the
457                          * current best fit is the left record. (By that we may
458                          * worsen the best fit we already had, bit this is not a
459                          * problem.)
460                          *
461                          * If the current best fit is not the left record,
462                          * all we can do is remember the fact that a merge
463                          * created a new candidate so that we can trigger
464                          * a second walk of the freelist if at the end of
465                          * the first walk we have not found any fit.
466                          * This way we can avoid expanding the database.
467                          */
468
469                         if (bestfit.rec_ptr == left_ptr) {
470                                 bestfit.rec_len = left_rec.rec_len;
471                         }
472
473                         if (left_rec.rec_len > length) {
474                                 merge_created_candidate = true;
475                         }
476
477                         modified = true;
478
479                         continue;
480                 }
481
482                 if (rec->rec_len >= length) {
483                         if (bestfit.rec_ptr == 0 ||
484                             rec->rec_len < bestfit.rec_len) {
485                                 bestfit.rec_len = rec->rec_len;
486                                 bestfit.rec_ptr = rec_ptr;
487                                 bestfit.last_ptr = last_ptr;
488                         }
489                 }
490
491                 /* move to the next record */
492                 last_ptr = rec_ptr;
493                 rec_ptr = rec->next;
494
495                 if (!modified) {
496                         bool ok;
497                         ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
498                         if (!ok) {
499                                 return 0;
500                         }
501                 }
502
503                 /* if we've found a record that is big enough, then
504                    stop searching if its also not too big. The
505                    definition of 'too big' changes as we scan
506                    through */
507                 if (bestfit.rec_len > 0 &&
508                     bestfit.rec_len < length * multiplier) {
509                         break;
510                 }
511
512                 /* this multiplier means we only extremely rarely
513                    search more than 50 or so records. At 50 records we
514                    accept records up to 11 times larger than what we
515                    want */
516                 multiplier *= 1.05;
517         }
518
519         if (bestfit.rec_ptr != 0) {
520                 if (tdb_rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
521                         return 0;
522                 }
523
524                 newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr,
525                                               rec, bestfit.last_ptr);
526                 return newrec_ptr;
527         }
528
529         if (merge_created_candidate) {
530                 goto again;
531         }
532
533         /* we didn't find enough space. See if we can expand the
534            database and if we can then try again */
535         if (tdb_expand(tdb, length + sizeof(*rec)) == 0)
536                 goto again;
537
538         return 0;
539 }
540
541 static bool tdb_alloc_dead(
542         struct tdb_context *tdb, int hash, tdb_len_t length,
543         tdb_off_t *rec_ptr, struct tdb_record *rec)
544 {
545         tdb_off_t last_ptr;
546
547         *rec_ptr = tdb_find_dead(tdb, hash, rec, length, &last_ptr);
548         if (*rec_ptr == 0) {
549                 return false;
550         }
551         /*
552          * Unlink the record from the hash chain, it's about to be moved into
553          * another one.
554          */
555         return (tdb_ofs_write(tdb, last_ptr, &rec->next) == 0);
556 }
557
558 static void tdb_purge_dead(struct tdb_context *tdb, uint32_t hash)
559 {
560         int max_dead_records = tdb->max_dead_records;
561
562         tdb->max_dead_records = 0;
563
564         tdb_trim_dead(tdb, hash);
565
566         tdb->max_dead_records = max_dead_records;
567 }
568
569 /*
570  * Chain "hash" is assumed to be locked
571  */
572
573 tdb_off_t tdb_allocate(struct tdb_context *tdb, int hash, tdb_len_t length,
574                        struct tdb_record *rec)
575 {
576         tdb_off_t ret;
577         uint32_t i;
578
579         if (tdb->max_dead_records == 0) {
580                 /*
581                  * No dead records to expect anywhere. Do the blocking
582                  * freelist lock without trying to steal from others
583                  */
584                 goto blocking_freelist_allocate;
585         }
586
587         /*
588          * The following loop tries to get the freelist lock nonblocking. If
589          * it gets the lock, allocate from there. If the freelist is busy,
590          * instead of waiting we try to steal dead records from other hash
591          * chains.
592          *
593          * Be aware that we do nonblocking locks on the other hash chains as
594          * well and fail gracefully. This way we avoid deadlocks (we block two
595          * hash chains, something which is pretty bad normally)
596          */
597
598         for (i=0; i<tdb->hash_size; i++) {
599
600                 int list;
601
602                 list = BUCKET(hash+i);
603
604                 if (tdb_lock_nonblock(tdb, list, F_WRLCK) == 0) {
605                         bool got_dead;
606
607                         got_dead = tdb_alloc_dead(tdb, list, length, &ret, rec);
608                         tdb_unlock(tdb, list, F_WRLCK);
609
610                         if (got_dead) {
611                                 return ret;
612                         }
613                 }
614
615                 if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == 0) {
616                         /*
617                          * Under the freelist lock take the chance to give
618                          * back our dead records.
619                          */
620                         tdb_purge_dead(tdb, hash);
621
622                         ret = tdb_allocate_from_freelist(tdb, length, rec);
623                         tdb_unlock(tdb, -1, F_WRLCK);
624                         return ret;
625                 }
626         }
627
628 blocking_freelist_allocate:
629
630         if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
631                 return 0;
632         }
633         /*
634          * Dead records can happen even if max_dead_records==0, they
635          * are older than the max_dead_records concept: They happen if
636          * tdb_delete happens concurrently with a traverse.
637          */
638         tdb_purge_dead(tdb, hash);
639         ret = tdb_allocate_from_freelist(tdb, length, rec);
640         tdb_unlock(tdb, -1, F_WRLCK);
641         return ret;
642 }
643
644 /**
645  * Merge adjacent records in the freelist.
646  */
647 static int tdb_freelist_merge_adjacent(struct tdb_context *tdb,
648                                        int *count_records, int *count_merged)
649 {
650         tdb_off_t cur, next;
651         int count = 0;
652         int merged = 0;
653         int ret;
654
655         ret = tdb_lock(tdb, -1, F_RDLCK);
656         if (ret == -1) {
657                 return -1;
658         }
659
660         cur = FREELIST_TOP;
661         while (tdb_ofs_read(tdb, cur, &next) == 0 && next != 0) {
662                 tdb_off_t next2;
663
664                 count++;
665
666                 ret = check_merge_ptr_with_left_record(tdb, next, &next2);
667                 if (ret == -1) {
668                         goto done;
669                 }
670                 if (ret == 1) {
671                         /*
672                          * merged:
673                          * now let cur->next point to next2 instead of next
674                          */
675
676                         ret = tdb_ofs_write(tdb, cur, &next2);
677                         if (ret != 0) {
678                                 goto done;
679                         }
680
681                         next = next2;
682                         merged++;
683                 }
684
685                 cur = next;
686         }
687
688         if (count_records != NULL) {
689                 *count_records = count;
690         }
691
692         if (count_merged != NULL) {
693                 *count_merged = merged;
694         }
695
696         ret = 0;
697
698 done:
699         tdb_unlock(tdb, -1, F_RDLCK);
700         return ret;
701 }
702
703 /**
704  * return the size of the freelist - no merging done
705  */
706 static int tdb_freelist_size_no_merge(struct tdb_context *tdb)
707 {
708         tdb_off_t ptr;
709         int count=0;
710
711         if (tdb_lock(tdb, -1, F_RDLCK) == -1) {
712                 return -1;
713         }
714
715         ptr = FREELIST_TOP;
716         while (tdb_ofs_read(tdb, ptr, &ptr) == 0 && ptr != 0) {
717                 count++;
718         }
719
720         tdb_unlock(tdb, -1, F_RDLCK);
721         return count;
722 }
723
724 /**
725  * return the size of the freelist - used to decide if we should repack
726  *
727  * As a side effect, adjacent records are merged unless the
728  * database is read-only, in order to reduce the fragmentation
729  * without repacking.
730  */
731 _PUBLIC_ int tdb_freelist_size(struct tdb_context *tdb)
732 {
733
734         int count = 0;
735
736         if (tdb->read_only) {
737                 count = tdb_freelist_size_no_merge(tdb);
738         } else {
739                 int ret;
740                 ret = tdb_freelist_merge_adjacent(tdb, &count, NULL);
741                 if (ret != 0) {
742                         return -1;
743                 }
744         }
745
746         return count;
747 }