tdb2: get rid of TDB1 mark and nonblock functions.
[ccan] / ccan / tdb2 / tdb1_transaction.c
1  /*
2    Unix SMB/CIFS implementation.
3
4    trivial database library
5
6    Copyright (C) Andrew Tridgell              2005
7
8      ** NOTE! The following LGPL license applies to the tdb
9      ** library. This does NOT imply that all of Samba is released
10      ** under the LGPL
11
12    This library is free software; you can redistribute it and/or
13    modify it under the terms of the GNU Lesser General Public
14    License as published by the Free Software Foundation; either
15    version 3 of the License, or (at your option) any later version.
16
17    This library is distributed in the hope that it will be useful,
18    but WITHOUT ANY WARRANTY; without even the implied warranty of
19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
20    Lesser General Public License for more details.
21
22    You should have received a copy of the GNU Lesser General Public
23    License along with this library; if not, see <http://www.gnu.org/licenses/>.
24 */
25
26 #include "tdb1_private.h"
27
28 /*
29   transaction design:
30
31   - only allow a single transaction at a time per database. This makes
32     using the transaction API simpler, as otherwise the caller would
33     have to cope with temporary failures in transactions that conflict
34     with other current transactions
35
36   - keep the transaction recovery information in the same file as the
37     database, using a special 'transaction recovery' record pointed at
38     by the header. This removes the need for extra journal files as
39     used by some other databases
40
41   - dynamically allocated the transaction recover record, re-using it
42     for subsequent transactions. If a larger record is needed then
43     tdb1_free() the old record to place it on the normal tdb freelist
44     before allocating the new record
45
46   - during transactions, keep a linked list of writes all that have
47     been performed by intercepting all tdb1_write() calls. The hooked
48     transaction versions of tdb1_read() and tdb1_write() check this
49     linked list and try to use the elements of the list in preference
50     to the real database.
51
52   - don't allow any locks to be held when a transaction starts,
53     otherwise we can end up with deadlock (plus lack of lock nesting
54     in posix locks would mean the lock is lost)
55
56   - if the caller gains a lock during the transaction but doesn't
57     release it then fail the commit
58
59   - allow for nested calls to tdb1_transaction_start(), re-using the
60     existing transaction record. If the inner transaction is cancelled
61     then a subsequent commit will fail
62
63   - keep a mirrored copy of the tdb hash chain heads to allow for the
64     fast hash heads scan on traverse, updating the mirrored copy in
65     the transaction version of tdb1_write
66
67   - allow callers to mix transaction and non-transaction use of tdb,
68     although once a transaction is started then an exclusive lock is
69     gained until the transaction is committed or cancelled
70
71   - the commit stategy involves first saving away all modified data
72     into a linearised buffer in the transaction recovery area, then
73     marking the transaction recovery area with a magic value to
74     indicate a valid recovery record. In total 4 fsync/msync calls are
75     needed per commit to prevent race conditions. It might be possible
76     to reduce this to 3 or even 2 with some more work.
77
78   - check for a valid recovery record on open of the tdb, while the
79     open lock is held. Automatically recover from the transaction
80     recovery area if needed, then continue with the open as
81     usual. This allows for smooth crash recovery with no administrator
82     intervention.
83
84   - if TDB1_NOSYNC is passed to flags in tdb1_open then transactions are
85     still available, but no transaction recovery area is used and no
86     fsync/msync calls are made.
87
88   - if TDB1_ALLOW_NESTING is passed to flags in tdb open, or added using
89     tdb1_add_flags() transaction nesting is enabled.
90     It resets the TDB1_DISALLOW_NESTING flag, as both cannot be used together.
91     The default is that transaction nesting is allowed.
92     Note: this default may change in future versions of tdb.
93
94     Beware. when transactions are nested a transaction successfully
95     completed with tdb1_transaction_commit() can be silently unrolled later.
96
97   - if TDB1_DISALLOW_NESTING is passed to flags in tdb open, or added using
98     tdb1_add_flags() transaction nesting is disabled.
99     It resets the TDB1_ALLOW_NESTING flag, as both cannot be used together.
100     An attempt create a nested transaction will fail with TDB1_ERR_NESTING.
101     The default is that transaction nesting is allowed.
102     Note: this default may change in future versions of tdb.
103 */
104
105
106 /*
107   hold the context of any current transaction
108 */
109 struct tdb1_transaction {
110         /* we keep a mirrored copy of the tdb hash heads here so
111            tdb1_next_hash_chain() can operate efficiently */
112         uint32_t *hash_heads;
113
114         /* the original io methods - used to do IOs to the real db */
115         const struct tdb1_methods *io_methods;
116
117         /* the list of transaction blocks. When a block is first
118            written to, it gets created in this list */
119         uint8_t **blocks;
120         uint32_t num_blocks;
121         uint32_t block_size;      /* bytes in each block */
122         uint32_t last_block_size; /* number of valid bytes in the last block */
123
124         /* non-zero when an internal transaction error has
125            occurred. All write operations will then fail until the
126            transaction is ended */
127         int transaction_error;
128
129         /* when inside a transaction we need to keep track of any
130            nested tdb1_transaction_start() calls, as these are allowed,
131            but don't create a new transaction */
132         int nesting;
133
134         /* set when a prepare has already occurred */
135         bool prepared;
136         tdb1_off_t magic_offset;
137
138         /* old file size before transaction */
139         tdb1_len_t old_map_size;
140
141         /* did we expand in this transaction */
142         bool expanded;
143 };
144
145
146 /*
147   read while in a transaction. We need to check first if the data is in our list
148   of transaction elements, then if not do a real read
149 */
150 static int transaction1_read(struct tdb1_context *tdb, tdb1_off_t off, void *buf,
151                              tdb1_len_t len, int cv)
152 {
153         uint32_t blk;
154
155         /* break it down into block sized ops */
156         while (len + (off % tdb->transaction->block_size) > tdb->transaction->block_size) {
157                 tdb1_len_t len2 = tdb->transaction->block_size - (off % tdb->transaction->block_size);
158                 if (transaction1_read(tdb, off, buf, len2, cv) != 0) {
159                         return -1;
160                 }
161                 len -= len2;
162                 off += len2;
163                 buf = (void *)(len2 + (char *)buf);
164         }
165
166         if (len == 0) {
167                 return 0;
168         }
169
170         blk = off / tdb->transaction->block_size;
171
172         /* see if we have it in the block list */
173         if (tdb->transaction->num_blocks <= blk ||
174             tdb->transaction->blocks[blk] == NULL) {
175                 /* nope, do a real read */
176                 if (tdb->transaction->io_methods->tdb1_read(tdb, off, buf, len, cv) != 0) {
177                         goto fail;
178                 }
179                 return 0;
180         }
181
182         /* it is in the block list. Now check for the last block */
183         if (blk == tdb->transaction->num_blocks-1) {
184                 if (len > tdb->transaction->last_block_size) {
185                         goto fail;
186                 }
187         }
188
189         /* now copy it out of this block */
190         memcpy(buf, tdb->transaction->blocks[blk] + (off % tdb->transaction->block_size), len);
191         if (cv) {
192                 tdb1_convert(buf, len);
193         }
194         return 0;
195
196 fail:
197         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "transaction_read: failed at off=%d len=%d\n", off, len));
198         tdb->ecode = TDB1_ERR_IO;
199         tdb->transaction->transaction_error = 1;
200         return -1;
201 }
202
203
204 /*
205   write while in a transaction
206 */
207 static int transaction1_write(struct tdb1_context *tdb, tdb1_off_t off,
208                              const void *buf, tdb1_len_t len)
209 {
210         uint32_t blk;
211
212         /* Only a commit is allowed on a prepared transaction */
213         if (tdb->transaction->prepared) {
214                 tdb->ecode = TDB1_ERR_EINVAL;
215                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "transaction_write: transaction already prepared, write not allowed\n"));
216                 tdb->transaction->transaction_error = 1;
217                 return -1;
218         }
219
220         /* if the write is to a hash head, then update the transaction
221            hash heads */
222         if (len == sizeof(tdb1_off_t) && off >= TDB1_FREELIST_TOP &&
223             off < TDB1_FREELIST_TOP+TDB1_HASHTABLE_SIZE(tdb)) {
224                 uint32_t chain = (off-TDB1_FREELIST_TOP) / sizeof(tdb1_off_t);
225                 memcpy(&tdb->transaction->hash_heads[chain], buf, len);
226         }
227
228         /* break it up into block sized chunks */
229         while (len + (off % tdb->transaction->block_size) > tdb->transaction->block_size) {
230                 tdb1_len_t len2 = tdb->transaction->block_size - (off % tdb->transaction->block_size);
231                 if (transaction1_write(tdb, off, buf, len2) != 0) {
232                         return -1;
233                 }
234                 len -= len2;
235                 off += len2;
236                 if (buf != NULL) {
237                         buf = (const void *)(len2 + (const char *)buf);
238                 }
239         }
240
241         if (len == 0) {
242                 return 0;
243         }
244
245         blk = off / tdb->transaction->block_size;
246         off = off % tdb->transaction->block_size;
247
248         if (tdb->transaction->num_blocks <= blk) {
249                 uint8_t **new_blocks;
250                 /* expand the blocks array */
251                 if (tdb->transaction->blocks == NULL) {
252                         new_blocks = (uint8_t **)malloc(
253                                 (blk+1)*sizeof(uint8_t *));
254                 } else {
255                         new_blocks = (uint8_t **)realloc(
256                                 tdb->transaction->blocks,
257                                 (blk+1)*sizeof(uint8_t *));
258                 }
259                 if (new_blocks == NULL) {
260                         tdb->ecode = TDB1_ERR_OOM;
261                         goto fail;
262                 }
263                 memset(&new_blocks[tdb->transaction->num_blocks], 0,
264                        (1+(blk - tdb->transaction->num_blocks))*sizeof(uint8_t *));
265                 tdb->transaction->blocks = new_blocks;
266                 tdb->transaction->num_blocks = blk+1;
267                 tdb->transaction->last_block_size = 0;
268         }
269
270         /* allocate and fill a block? */
271         if (tdb->transaction->blocks[blk] == NULL) {
272                 tdb->transaction->blocks[blk] = (uint8_t *)calloc(tdb->transaction->block_size, 1);
273                 if (tdb->transaction->blocks[blk] == NULL) {
274                         tdb->ecode = TDB1_ERR_OOM;
275                         tdb->transaction->transaction_error = 1;
276                         return -1;
277                 }
278                 if (tdb->transaction->old_map_size > blk * tdb->transaction->block_size) {
279                         tdb1_len_t len2 = tdb->transaction->block_size;
280                         if (len2 + (blk * tdb->transaction->block_size) > tdb->transaction->old_map_size) {
281                                 len2 = tdb->transaction->old_map_size - (blk * tdb->transaction->block_size);
282                         }
283                         if (tdb->transaction->io_methods->tdb1_read(tdb, blk * tdb->transaction->block_size,
284                                                                    tdb->transaction->blocks[blk],
285                                                                    len2, 0) != 0) {
286                                 SAFE_FREE(tdb->transaction->blocks[blk]);
287                                 tdb->ecode = TDB1_ERR_IO;
288                                 goto fail;
289                         }
290                         if (blk == tdb->transaction->num_blocks-1) {
291                                 tdb->transaction->last_block_size = len2;
292                         }
293                 }
294         }
295
296         /* overwrite part of an existing block */
297         if (buf == NULL) {
298                 memset(tdb->transaction->blocks[blk] + off, 0, len);
299         } else {
300                 memcpy(tdb->transaction->blocks[blk] + off, buf, len);
301         }
302         if (blk == tdb->transaction->num_blocks-1) {
303                 if (len + off > tdb->transaction->last_block_size) {
304                         tdb->transaction->last_block_size = len + off;
305                 }
306         }
307
308         return 0;
309
310 fail:
311         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "transaction_write: failed at off=%d len=%d\n",
312                  (blk*tdb->transaction->block_size) + off, len));
313         tdb->transaction->transaction_error = 1;
314         return -1;
315 }
316
317
318 /*
319   write while in a transaction - this varient never expands the transaction blocks, it only
320   updates existing blocks. This means it cannot change the recovery size
321 */
322 static int transaction1_write_existing(struct tdb1_context *tdb, tdb1_off_t off,
323                                       const void *buf, tdb1_len_t len)
324 {
325         uint32_t blk;
326
327         /* break it up into block sized chunks */
328         while (len + (off % tdb->transaction->block_size) > tdb->transaction->block_size) {
329                 tdb1_len_t len2 = tdb->transaction->block_size - (off % tdb->transaction->block_size);
330                 if (transaction1_write_existing(tdb, off, buf, len2) != 0) {
331                         return -1;
332                 }
333                 len -= len2;
334                 off += len2;
335                 if (buf != NULL) {
336                         buf = (const void *)(len2 + (const char *)buf);
337                 }
338         }
339
340         if (len == 0) {
341                 return 0;
342         }
343
344         blk = off / tdb->transaction->block_size;
345         off = off % tdb->transaction->block_size;
346
347         if (tdb->transaction->num_blocks <= blk ||
348             tdb->transaction->blocks[blk] == NULL) {
349                 return 0;
350         }
351
352         if (blk == tdb->transaction->num_blocks-1 &&
353             off + len > tdb->transaction->last_block_size) {
354                 if (off >= tdb->transaction->last_block_size) {
355                         return 0;
356                 }
357                 len = tdb->transaction->last_block_size - off;
358         }
359
360         /* overwrite part of an existing block */
361         memcpy(tdb->transaction->blocks[blk] + off, buf, len);
362
363         return 0;
364 }
365
366
367 /*
368   accelerated hash chain head search, using the cached hash heads
369 */
370 static void transaction1_next_hash_chain(struct tdb1_context *tdb, uint32_t *chain)
371 {
372         uint32_t h = *chain;
373         for (;h < tdb->header.hash_size;h++) {
374                 /* the +1 takes account of the freelist */
375                 if (0 != tdb->transaction->hash_heads[h+1]) {
376                         break;
377                 }
378         }
379         (*chain) = h;
380 }
381
382 /*
383   out of bounds check during a transaction
384 */
385 static int transaction1_oob(struct tdb1_context *tdb, tdb1_off_t len, int probe)
386 {
387         if (len <= tdb->map_size) {
388                 return 0;
389         }
390         tdb->ecode = TDB1_ERR_IO;
391         return -1;
392 }
393
394 /*
395   transaction version of tdb1_expand().
396 */
397 static int transaction1_expand_file(struct tdb1_context *tdb, tdb1_off_t size,
398                                     tdb1_off_t addition)
399 {
400         /* add a write to the transaction elements, so subsequent
401            reads see the zero data */
402         if (transaction1_write(tdb, size, NULL, addition) != 0) {
403                 return -1;
404         }
405
406         tdb->transaction->expanded = true;
407
408         return 0;
409 }
410
411 static const struct tdb1_methods transaction1_methods = {
412         transaction1_read,
413         transaction1_write,
414         transaction1_next_hash_chain,
415         transaction1_oob,
416         transaction1_expand_file,
417 };
418
419
420 /*
421   start a tdb transaction. No token is returned, as only a single
422   transaction is allowed to be pending per tdb1_context
423 */
424 static int _tdb1_transaction_start(struct tdb1_context *tdb)
425 {
426         /* some sanity checks */
427         if (tdb->read_only || (tdb->flags & TDB1_INTERNAL) || tdb->traverse_read) {
428                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_start: cannot start a transaction on a read-only or internal db\n"));
429                 tdb->ecode = TDB1_ERR_EINVAL;
430                 return -1;
431         }
432
433         /* cope with nested tdb1_transaction_start() calls */
434         if (tdb->transaction != NULL) {
435                 if (!(tdb->flags & TDB1_ALLOW_NESTING)) {
436                         tdb->ecode = TDB1_ERR_NESTING;
437                         return -1;
438                 }
439                 tdb->transaction->nesting++;
440                 TDB1_LOG((tdb, TDB1_DEBUG_TRACE, "tdb1_transaction_start: nesting %d\n",
441                          tdb->transaction->nesting));
442                 return 0;
443         }
444
445         if (tdb1_have_extra_locks(tdb)) {
446                 /* the caller must not have any locks when starting a
447                    transaction as otherwise we'll be screwed by lack
448                    of nested locks in posix */
449                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_start: cannot start a transaction with locks held\n"));
450                 tdb->ecode = TDB1_ERR_LOCK;
451                 return -1;
452         }
453
454         if (tdb->travlocks.next != NULL) {
455                 /* you cannot use transactions inside a traverse (although you can use
456                    traverse inside a transaction) as otherwise you can end up with
457                    deadlock */
458                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_start: cannot start a transaction within a traverse\n"));
459                 tdb->ecode = TDB1_ERR_LOCK;
460                 return -1;
461         }
462
463         tdb->transaction = (struct tdb1_transaction *)
464                 calloc(sizeof(struct tdb1_transaction), 1);
465         if (tdb->transaction == NULL) {
466                 tdb->ecode = TDB1_ERR_OOM;
467                 return -1;
468         }
469
470         /* a page at a time seems like a reasonable compromise between compactness and efficiency */
471         tdb->transaction->block_size = tdb->page_size;
472
473         /* get the transaction write lock. This is a blocking lock. As
474            discussed with Volker, there are a number of ways we could
475            make this async, which we will probably do in the future */
476         if (tdb1_transaction_lock(tdb, F_WRLCK, TDB1_LOCK_WAIT) == -1) {
477                 SAFE_FREE(tdb->transaction->blocks);
478                 SAFE_FREE(tdb->transaction);
479                 return -1;
480         }
481
482         /* get a read lock from the freelist to the end of file. This
483            is upgraded to a write lock during the commit */
484         if (tdb1_allrecord_lock(tdb, F_RDLCK, TDB1_LOCK_WAIT, true) == -1) {
485                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_start: failed to get hash locks\n"));
486                 goto fail_allrecord_lock;
487         }
488
489         /* setup a copy of the hash table heads so the hash scan in
490            traverse can be fast */
491         tdb->transaction->hash_heads = (uint32_t *)
492                 calloc(tdb->header.hash_size+1, sizeof(uint32_t));
493         if (tdb->transaction->hash_heads == NULL) {
494                 tdb->ecode = TDB1_ERR_OOM;
495                 goto fail;
496         }
497         if (tdb->methods->tdb1_read(tdb, TDB1_FREELIST_TOP, tdb->transaction->hash_heads,
498                                    TDB1_HASHTABLE_SIZE(tdb), 0) != 0) {
499                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_start: failed to read hash heads\n"));
500                 tdb->ecode = TDB1_ERR_IO;
501                 goto fail;
502         }
503
504         /* make sure we know about any file expansions already done by
505            anyone else */
506         tdb->methods->tdb1_oob(tdb, tdb->map_size + 1, 1);
507         tdb->transaction->old_map_size = tdb->map_size;
508
509         /* finally hook the io methods, replacing them with
510            transaction specific methods */
511         tdb->transaction->io_methods = tdb->methods;
512         tdb->methods = &transaction1_methods;
513
514         return 0;
515
516 fail:
517         tdb1_allrecord_unlock(tdb, F_RDLCK);
518 fail_allrecord_lock:
519         tdb1_transaction_unlock(tdb, F_WRLCK);
520         SAFE_FREE(tdb->transaction->blocks);
521         SAFE_FREE(tdb->transaction->hash_heads);
522         SAFE_FREE(tdb->transaction);
523         return -1;
524 }
525
526 int tdb1_transaction_start(struct tdb1_context *tdb)
527 {
528         return _tdb1_transaction_start(tdb);
529 }
530
531 /*
532   sync to disk
533 */
534 static int transaction1_sync(struct tdb1_context *tdb, tdb1_off_t offset, tdb1_len_t length)
535 {
536         if (tdb->flags & TDB1_NOSYNC) {
537                 return 0;
538         }
539
540 #if HAVE_FDATASYNC
541         if (fdatasync(tdb->fd) != 0) {
542 #else
543         if (fsync(tdb->fd) != 0) {
544 #endif
545                 tdb->ecode = TDB1_ERR_IO;
546                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction: fsync failed\n"));
547                 return -1;
548         }
549 #if HAVE_MMAP
550         if (tdb->map_ptr) {
551                 tdb1_off_t moffset = offset & ~(tdb->page_size-1);
552                 if (msync(moffset + (char *)tdb->map_ptr,
553                           length + (offset - moffset), MS_SYNC) != 0) {
554                         tdb->ecode = TDB1_ERR_IO;
555                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction: msync failed - %s\n",
556                                  strerror(errno)));
557                         return -1;
558                 }
559         }
560 #endif
561         return 0;
562 }
563
564
565 static int _tdb1_transaction_cancel(struct tdb1_context *tdb)
566 {
567         int i, ret = 0;
568
569         if (tdb->transaction == NULL) {
570                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_cancel: no transaction\n"));
571                 return -1;
572         }
573
574         if (tdb->transaction->nesting != 0) {
575                 tdb->transaction->transaction_error = 1;
576                 tdb->transaction->nesting--;
577                 return 0;
578         }
579
580         tdb->map_size = tdb->transaction->old_map_size;
581
582         /* free all the transaction blocks */
583         for (i=0;i<tdb->transaction->num_blocks;i++) {
584                 if (tdb->transaction->blocks[i] != NULL) {
585                         free(tdb->transaction->blocks[i]);
586                 }
587         }
588         SAFE_FREE(tdb->transaction->blocks);
589
590         if (tdb->transaction->magic_offset) {
591                 const struct tdb1_methods *methods = tdb->transaction->io_methods;
592                 const uint32_t invalid = TDB1_RECOVERY_INVALID_MAGIC;
593
594                 /* remove the recovery marker */
595                 if (methods->tdb1_write(tdb, tdb->transaction->magic_offset, &invalid, 4) == -1 ||
596                 transaction1_sync(tdb, tdb->transaction->magic_offset, 4) == -1) {
597                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_cancel: failed to remove recovery magic\n"));
598                         ret = -1;
599                 }
600         }
601
602         /* This also removes the OPEN_LOCK, if we have it. */
603         tdb1_release_transaction_locks(tdb);
604
605         /* restore the normal io methods */
606         tdb->methods = tdb->transaction->io_methods;
607
608         SAFE_FREE(tdb->transaction->hash_heads);
609         SAFE_FREE(tdb->transaction);
610
611         return ret;
612 }
613
614 /*
615   cancel the current transaction
616 */
617 int tdb1_transaction_cancel(struct tdb1_context *tdb)
618 {
619         return _tdb1_transaction_cancel(tdb);
620 }
621
622 /*
623   work out how much space the linearised recovery data will consume
624 */
625 static tdb1_len_t tdb1_recovery_size(struct tdb1_context *tdb)
626 {
627         tdb1_len_t recovery_size = 0;
628         int i;
629
630         recovery_size = sizeof(uint32_t);
631         for (i=0;i<tdb->transaction->num_blocks;i++) {
632                 if (i * tdb->transaction->block_size >= tdb->transaction->old_map_size) {
633                         break;
634                 }
635                 if (tdb->transaction->blocks[i] == NULL) {
636                         continue;
637                 }
638                 recovery_size += 2*sizeof(tdb1_off_t);
639                 if (i == tdb->transaction->num_blocks-1) {
640                         recovery_size += tdb->transaction->last_block_size;
641                 } else {
642                         recovery_size += tdb->transaction->block_size;
643                 }
644         }
645
646         return recovery_size;
647 }
648
649 int tdb1_recovery_area(struct tdb1_context *tdb,
650                       const struct tdb1_methods *methods,
651                       tdb1_off_t *recovery_offset,
652                       struct tdb1_record *rec)
653 {
654         if (tdb1_ofs_read(tdb, TDB1_RECOVERY_HEAD, recovery_offset) == -1) {
655                 return -1;
656         }
657
658         if (*recovery_offset == 0) {
659                 rec->rec_len = 0;
660                 return 0;
661         }
662
663         if (methods->tdb1_read(tdb, *recovery_offset, rec, sizeof(*rec),
664                               TDB1_DOCONV()) == -1) {
665                 return -1;
666         }
667
668         /* ignore invalid recovery regions: can happen in crash */
669         if (rec->magic != TDB1_RECOVERY_MAGIC &&
670             rec->magic != TDB1_RECOVERY_INVALID_MAGIC) {
671                 *recovery_offset = 0;
672                 rec->rec_len = 0;
673         }
674         return 0;
675 }
676
677 /*
678   allocate the recovery area, or use an existing recovery area if it is
679   large enough
680 */
681 static int tdb1_recovery_allocate(struct tdb1_context *tdb,
682                                  tdb1_len_t *recovery_size,
683                                  tdb1_off_t *recovery_offset,
684                                  tdb1_len_t *recovery_max_size)
685 {
686         struct tdb1_record rec;
687         const struct tdb1_methods *methods = tdb->transaction->io_methods;
688         tdb1_off_t recovery_head;
689
690         if (tdb1_recovery_area(tdb, methods, &recovery_head, &rec) == -1) {
691                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_recovery_allocate: failed to read recovery head\n"));
692                 return -1;
693         }
694
695         *recovery_size = tdb1_recovery_size(tdb);
696
697         if (recovery_head != 0 && *recovery_size <= rec.rec_len) {
698                 /* it fits in the existing area */
699                 *recovery_max_size = rec.rec_len;
700                 *recovery_offset = recovery_head;
701                 return 0;
702         }
703
704         /* we need to free up the old recovery area, then allocate a
705            new one at the end of the file. Note that we cannot use
706            tdb1_allocate() to allocate the new one as that might return
707            us an area that is being currently used (as of the start of
708            the transaction) */
709         if (recovery_head != 0) {
710                 if (tdb1_free(tdb, recovery_head, &rec) == -1) {
711                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_recovery_allocate: failed to free previous recovery area\n"));
712                         return -1;
713                 }
714         }
715
716         /* the tdb1_free() call might have increased the recovery size */
717         *recovery_size = tdb1_recovery_size(tdb);
718
719         /* round up to a multiple of page size */
720         *recovery_max_size = TDB1_ALIGN(sizeof(rec) + *recovery_size, tdb->page_size) - sizeof(rec);
721         *recovery_offset = tdb->map_size;
722         recovery_head = *recovery_offset;
723
724         if (methods->tdb1_expand_file(tdb, tdb->transaction->old_map_size,
725                                      (tdb->map_size - tdb->transaction->old_map_size) +
726                                      sizeof(rec) + *recovery_max_size) == -1) {
727                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_recovery_allocate: failed to create recovery area\n"));
728                 return -1;
729         }
730
731         /* remap the file (if using mmap) */
732         methods->tdb1_oob(tdb, tdb->map_size + 1, 1);
733
734         /* we have to reset the old map size so that we don't try to expand the file
735            again in the transaction commit, which would destroy the recovery area */
736         tdb->transaction->old_map_size = tdb->map_size;
737
738         /* write the recovery header offset and sync - we can sync without a race here
739            as the magic ptr in the recovery record has not been set */
740         TDB1_CONV(recovery_head);
741         if (methods->tdb1_write(tdb, TDB1_RECOVERY_HEAD,
742                                &recovery_head, sizeof(tdb1_off_t)) == -1) {
743                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_recovery_allocate: failed to write recovery head\n"));
744                 return -1;
745         }
746         if (transaction1_write_existing(tdb, TDB1_RECOVERY_HEAD, &recovery_head, sizeof(tdb1_off_t)) == -1) {
747                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_recovery_allocate: failed to write recovery head\n"));
748                 return -1;
749         }
750
751         return 0;
752 }
753
754
755 /*
756   setup the recovery data that will be used on a crash during commit
757 */
758 static int transaction1_setup_recovery(struct tdb1_context *tdb,
759                                        tdb1_off_t *magic_offset)
760 {
761         tdb1_len_t recovery_size;
762         unsigned char *data, *p;
763         const struct tdb1_methods *methods = tdb->transaction->io_methods;
764         struct tdb1_record *rec;
765         tdb1_off_t recovery_offset, recovery_max_size;
766         tdb1_off_t old_map_size = tdb->transaction->old_map_size;
767         uint32_t magic, tailer;
768         int i;
769
770         /*
771           check that the recovery area has enough space
772         */
773         if (tdb1_recovery_allocate(tdb, &recovery_size,
774                                   &recovery_offset, &recovery_max_size) == -1) {
775                 return -1;
776         }
777
778         data = (unsigned char *)malloc(recovery_size + sizeof(*rec));
779         if (data == NULL) {
780                 tdb->ecode = TDB1_ERR_OOM;
781                 return -1;
782         }
783
784         rec = (struct tdb1_record *)data;
785         memset(rec, 0, sizeof(*rec));
786
787         rec->magic    = TDB1_RECOVERY_INVALID_MAGIC;
788         rec->data_len = recovery_size;
789         rec->rec_len  = recovery_max_size;
790         rec->key_len  = old_map_size;
791         TDB1_CONV(*rec);
792
793         /* build the recovery data into a single blob to allow us to do a single
794            large write, which should be more efficient */
795         p = data + sizeof(*rec);
796         for (i=0;i<tdb->transaction->num_blocks;i++) {
797                 tdb1_off_t offset;
798                 tdb1_len_t length;
799
800                 if (tdb->transaction->blocks[i] == NULL) {
801                         continue;
802                 }
803
804                 offset = i * tdb->transaction->block_size;
805                 length = tdb->transaction->block_size;
806                 if (i == tdb->transaction->num_blocks-1) {
807                         length = tdb->transaction->last_block_size;
808                 }
809
810                 if (offset >= old_map_size) {
811                         continue;
812                 }
813                 if (offset + length > tdb->transaction->old_map_size) {
814                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_setup_recovery: transaction data over new region boundary\n"));
815                         free(data);
816                         tdb->ecode = TDB1_ERR_CORRUPT;
817                         return -1;
818                 }
819                 memcpy(p, &offset, 4);
820                 memcpy(p+4, &length, 4);
821                 if (TDB1_DOCONV()) {
822                         tdb1_convert(p, 8);
823                 }
824                 /* the recovery area contains the old data, not the
825                    new data, so we have to call the original tdb1_read
826                    method to get it */
827                 if (methods->tdb1_read(tdb, offset, p + 8, length, 0) != 0) {
828                         free(data);
829                         tdb->ecode = TDB1_ERR_IO;
830                         return -1;
831                 }
832                 p += 8 + length;
833         }
834
835         /* and the tailer */
836         tailer = sizeof(*rec) + recovery_max_size;
837         memcpy(p, &tailer, 4);
838         if (TDB1_DOCONV()) {
839                 tdb1_convert(p, 4);
840         }
841
842         /* write the recovery data to the recovery area */
843         if (methods->tdb1_write(tdb, recovery_offset, data, sizeof(*rec) + recovery_size) == -1) {
844                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_setup_recovery: failed to write recovery data\n"));
845                 free(data);
846                 tdb->ecode = TDB1_ERR_IO;
847                 return -1;
848         }
849         if (transaction1_write_existing(tdb, recovery_offset, data, sizeof(*rec) + recovery_size) == -1) {
850                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_setup_recovery: failed to write secondary recovery data\n"));
851                 free(data);
852                 tdb->ecode = TDB1_ERR_IO;
853                 return -1;
854         }
855
856         /* as we don't have ordered writes, we have to sync the recovery
857            data before we update the magic to indicate that the recovery
858            data is present */
859         if (transaction1_sync(tdb, recovery_offset, sizeof(*rec) + recovery_size) == -1) {
860                 free(data);
861                 return -1;
862         }
863
864         free(data);
865
866         magic = TDB1_RECOVERY_MAGIC;
867         TDB1_CONV(magic);
868
869         *magic_offset = recovery_offset + offsetof(struct tdb1_record, magic);
870
871         if (methods->tdb1_write(tdb, *magic_offset, &magic, sizeof(magic)) == -1) {
872                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_setup_recovery: failed to write recovery magic\n"));
873                 tdb->ecode = TDB1_ERR_IO;
874                 return -1;
875         }
876         if (transaction1_write_existing(tdb, *magic_offset, &magic, sizeof(magic)) == -1) {
877                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_setup_recovery: failed to write secondary recovery magic\n"));
878                 tdb->ecode = TDB1_ERR_IO;
879                 return -1;
880         }
881
882         /* ensure the recovery magic marker is on disk */
883         if (transaction1_sync(tdb, *magic_offset, sizeof(magic)) == -1) {
884                 return -1;
885         }
886
887         return 0;
888 }
889
890 static int _tdb1_transaction_prepare_commit(struct tdb1_context *tdb)
891 {
892         const struct tdb1_methods *methods;
893
894         if (tdb->transaction == NULL) {
895                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_prepare_commit: no transaction\n"));
896                 return -1;
897         }
898
899         if (tdb->transaction->prepared) {
900                 tdb->ecode = TDB1_ERR_EINVAL;
901                 _tdb1_transaction_cancel(tdb);
902                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_prepare_commit: transaction already prepared\n"));
903                 return -1;
904         }
905
906         if (tdb->transaction->transaction_error) {
907                 tdb->ecode = TDB1_ERR_IO;
908                 _tdb1_transaction_cancel(tdb);
909                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_prepare_commit: transaction error pending\n"));
910                 return -1;
911         }
912
913
914         if (tdb->transaction->nesting != 0) {
915                 return 0;
916         }
917
918         /* check for a null transaction */
919         if (tdb->transaction->blocks == NULL) {
920                 return 0;
921         }
922
923         methods = tdb->transaction->io_methods;
924
925         /* if there are any locks pending then the caller has not
926            nested their locks properly, so fail the transaction */
927         if (tdb1_have_extra_locks(tdb)) {
928                 tdb->ecode = TDB1_ERR_LOCK;
929                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_prepare_commit: locks pending on commit\n"));
930                 _tdb1_transaction_cancel(tdb);
931                 return -1;
932         }
933
934         /* upgrade the main transaction lock region to a write lock */
935         if (tdb1_allrecord_upgrade(tdb) == -1) {
936                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_prepare_commit: failed to upgrade hash locks\n"));
937                 _tdb1_transaction_cancel(tdb);
938                 return -1;
939         }
940
941         /* get the open lock - this prevents new users attaching to the database
942            during the commit */
943         if (tdb1_nest_lock(tdb, TDB1_OPEN_LOCK, F_WRLCK, TDB1_LOCK_WAIT) == -1) {
944                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_prepare_commit: failed to get open lock\n"));
945                 _tdb1_transaction_cancel(tdb);
946                 return -1;
947         }
948
949         if (!(tdb->flags & TDB1_NOSYNC)) {
950                 /* write the recovery data to the end of the file */
951                 if (transaction1_setup_recovery(tdb, &tdb->transaction->magic_offset) == -1) {
952                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_prepare_commit: failed to setup recovery data\n"));
953                         _tdb1_transaction_cancel(tdb);
954                         return -1;
955                 }
956         }
957
958         tdb->transaction->prepared = true;
959
960         /* expand the file to the new size if needed */
961         if (tdb->map_size != tdb->transaction->old_map_size) {
962                 if (methods->tdb1_expand_file(tdb, tdb->transaction->old_map_size,
963                                              tdb->map_size -
964                                              tdb->transaction->old_map_size) == -1) {
965                         tdb->ecode = TDB1_ERR_IO;
966                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_prepare_commit: expansion failed\n"));
967                         _tdb1_transaction_cancel(tdb);
968                         return -1;
969                 }
970                 tdb->map_size = tdb->transaction->old_map_size;
971                 methods->tdb1_oob(tdb, tdb->map_size + 1, 1);
972         }
973
974         /* Keep the open lock until the actual commit */
975
976         return 0;
977 }
978
979 /*
980    prepare to commit the current transaction
981 */
982 int tdb1_transaction_prepare_commit(struct tdb1_context *tdb)
983 {
984         return _tdb1_transaction_prepare_commit(tdb);
985 }
986
987 /* A repack is worthwhile if the largest is less than half total free. */
988 static bool repack_worthwhile(struct tdb1_context *tdb)
989 {
990         tdb1_off_t ptr;
991         struct tdb1_record rec;
992         tdb1_len_t total = 0, largest = 0;
993
994         if (tdb1_ofs_read(tdb, TDB1_FREELIST_TOP, &ptr) == -1) {
995                 return false;
996         }
997
998         while (ptr != 0 && tdb1_rec_free_read(tdb, ptr, &rec) == 0) {
999                 total += rec.rec_len;
1000                 if (rec.rec_len > largest) {
1001                         largest = rec.rec_len;
1002                 }
1003                 ptr = rec.next;
1004         }
1005
1006         return total > largest * 2;
1007 }
1008
1009 /*
1010   commit the current transaction
1011 */
1012 int tdb1_transaction_commit(struct tdb1_context *tdb)
1013 {
1014         const struct tdb1_methods *methods;
1015         int i;
1016         bool need_repack = false;
1017
1018         if (tdb->transaction == NULL) {
1019                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_commit: no transaction\n"));
1020                 return -1;
1021         }
1022
1023         if (tdb->transaction->transaction_error) {
1024                 tdb->ecode = TDB1_ERR_IO;
1025                 _tdb1_transaction_cancel(tdb);
1026                 TDB1_LOG((tdb, TDB1_DEBUG_ERROR, "tdb1_transaction_commit: transaction error pending\n"));
1027                 return -1;
1028         }
1029
1030
1031         if (tdb->transaction->nesting != 0) {
1032                 tdb->transaction->nesting--;
1033                 return 0;
1034         }
1035
1036         /* check for a null transaction */
1037         if (tdb->transaction->blocks == NULL) {
1038                 _tdb1_transaction_cancel(tdb);
1039                 return 0;
1040         }
1041
1042         if (!tdb->transaction->prepared) {
1043                 int ret = _tdb1_transaction_prepare_commit(tdb);
1044                 if (ret)
1045                         return ret;
1046         }
1047
1048         methods = tdb->transaction->io_methods;
1049
1050         /* perform all the writes */
1051         for (i=0;i<tdb->transaction->num_blocks;i++) {
1052                 tdb1_off_t offset;
1053                 tdb1_len_t length;
1054
1055                 if (tdb->transaction->blocks[i] == NULL) {
1056                         continue;
1057                 }
1058
1059                 offset = i * tdb->transaction->block_size;
1060                 length = tdb->transaction->block_size;
1061                 if (i == tdb->transaction->num_blocks-1) {
1062                         length = tdb->transaction->last_block_size;
1063                 }
1064
1065                 if (methods->tdb1_write(tdb, offset, tdb->transaction->blocks[i], length) == -1) {
1066                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_commit: write failed during commit\n"));
1067
1068                         /* we've overwritten part of the data and
1069                            possibly expanded the file, so we need to
1070                            run the crash recovery code */
1071                         tdb->methods = methods;
1072                         tdb1_transaction_recover(tdb);
1073
1074                         _tdb1_transaction_cancel(tdb);
1075
1076                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_commit: write failed\n"));
1077                         return -1;
1078                 }
1079                 SAFE_FREE(tdb->transaction->blocks[i]);
1080         }
1081
1082         /* Do this before we drop lock or blocks. */
1083         if (tdb->transaction->expanded) {
1084                 need_repack = repack_worthwhile(tdb);
1085         }
1086
1087         SAFE_FREE(tdb->transaction->blocks);
1088         tdb->transaction->num_blocks = 0;
1089
1090         /* ensure the new data is on disk */
1091         if (transaction1_sync(tdb, 0, tdb->map_size) == -1) {
1092                 return -1;
1093         }
1094
1095         /*
1096           TODO: maybe write to some dummy hdr field, or write to magic
1097           offset without mmap, before the last sync, instead of the
1098           utime() call
1099         */
1100
1101         /* on some systems (like Linux 2.6.x) changes via mmap/msync
1102            don't change the mtime of the file, this means the file may
1103            not be backed up (as tdb rounding to block sizes means that
1104            file size changes are quite rare too). The following forces
1105            mtime changes when a transaction completes */
1106 #if HAVE_UTIME
1107         utime(tdb->name, NULL);
1108 #endif
1109
1110         /* use a transaction cancel to free memory and remove the
1111            transaction locks */
1112         _tdb1_transaction_cancel(tdb);
1113
1114         if (need_repack) {
1115                 return tdb1_repack(tdb);
1116         }
1117
1118         return 0;
1119 }
1120
1121
1122 /*
1123   recover from an aborted transaction. Must be called with exclusive
1124   database write access already established (including the open
1125   lock to prevent new processes attaching)
1126 */
1127 int tdb1_transaction_recover(struct tdb1_context *tdb)
1128 {
1129         tdb1_off_t recovery_head, recovery_eof;
1130         unsigned char *data, *p;
1131         uint32_t zero = 0;
1132         struct tdb1_record rec;
1133
1134         /* find the recovery area */
1135         if (tdb1_ofs_read(tdb, TDB1_RECOVERY_HEAD, &recovery_head) == -1) {
1136                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to read recovery head\n"));
1137                 tdb->ecode = TDB1_ERR_IO;
1138                 return -1;
1139         }
1140
1141         if (recovery_head == 0) {
1142                 /* we have never allocated a recovery record */
1143                 return 0;
1144         }
1145
1146         /* read the recovery record */
1147         if (tdb->methods->tdb1_read(tdb, recovery_head, &rec,
1148                                    sizeof(rec), TDB1_DOCONV()) == -1) {
1149                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to read recovery record\n"));
1150                 tdb->ecode = TDB1_ERR_IO;
1151                 return -1;
1152         }
1153
1154         if (rec.magic != TDB1_RECOVERY_MAGIC) {
1155                 /* there is no valid recovery data */
1156                 return 0;
1157         }
1158
1159         if (tdb->read_only) {
1160                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: attempt to recover read only database\n"));
1161                 tdb->ecode = TDB1_ERR_CORRUPT;
1162                 return -1;
1163         }
1164
1165         recovery_eof = rec.key_len;
1166
1167         data = (unsigned char *)malloc(rec.data_len);
1168         if (data == NULL) {
1169                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to allocate recovery data\n"));
1170                 tdb->ecode = TDB1_ERR_OOM;
1171                 return -1;
1172         }
1173
1174         /* read the full recovery data */
1175         if (tdb->methods->tdb1_read(tdb, recovery_head + sizeof(rec), data,
1176                                    rec.data_len, 0) == -1) {
1177                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to read recovery data\n"));
1178                 tdb->ecode = TDB1_ERR_IO;
1179                 return -1;
1180         }
1181
1182         /* recover the file data */
1183         p = data;
1184         while (p+8 < data + rec.data_len) {
1185                 uint32_t ofs, len;
1186                 if (TDB1_DOCONV()) {
1187                         tdb1_convert(p, 8);
1188                 }
1189                 memcpy(&ofs, p, 4);
1190                 memcpy(&len, p+4, 4);
1191
1192                 if (tdb->methods->tdb1_write(tdb, ofs, p+8, len) == -1) {
1193                         free(data);
1194                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to recover %d bytes at offset %d\n", len, ofs));
1195                         tdb->ecode = TDB1_ERR_IO;
1196                         return -1;
1197                 }
1198                 p += 8 + len;
1199         }
1200
1201         free(data);
1202
1203         if (transaction1_sync(tdb, 0, tdb->map_size) == -1) {
1204                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to sync recovery\n"));
1205                 tdb->ecode = TDB1_ERR_IO;
1206                 return -1;
1207         }
1208
1209         /* if the recovery area is after the recovered eof then remove it */
1210         if (recovery_eof <= recovery_head) {
1211                 if (tdb1_ofs_write(tdb, TDB1_RECOVERY_HEAD, &zero) == -1) {
1212                         TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to remove recovery head\n"));
1213                         tdb->ecode = TDB1_ERR_IO;
1214                         return -1;
1215                 }
1216         }
1217
1218         /* remove the recovery magic */
1219         if (tdb1_ofs_write(tdb, recovery_head + offsetof(struct tdb1_record, magic),
1220                           &zero) == -1) {
1221                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to remove recovery magic\n"));
1222                 tdb->ecode = TDB1_ERR_IO;
1223                 return -1;
1224         }
1225
1226         if (transaction1_sync(tdb, 0, recovery_eof) == -1) {
1227                 TDB1_LOG((tdb, TDB1_DEBUG_FATAL, "tdb1_transaction_recover: failed to sync2 recovery\n"));
1228                 tdb->ecode = TDB1_ERR_IO;
1229                 return -1;
1230         }
1231
1232         TDB1_LOG((tdb, TDB1_DEBUG_TRACE, "tdb1_transaction_recover: recovered %d byte database\n",
1233                  recovery_eof));
1234
1235         /* all done */
1236         return 0;
1237 }
1238
1239 /* Any I/O failures we say "needs recovery". */
1240 bool tdb1_needs_recovery(struct tdb1_context *tdb)
1241 {
1242         tdb1_off_t recovery_head;
1243         struct tdb1_record rec;
1244
1245         /* find the recovery area */
1246         if (tdb1_ofs_read(tdb, TDB1_RECOVERY_HEAD, &recovery_head) == -1) {
1247                 return true;
1248         }
1249
1250         if (recovery_head == 0) {
1251                 /* we have never allocated a recovery record */
1252                 return false;
1253         }
1254
1255         /* read the recovery record */
1256         if (tdb->methods->tdb1_read(tdb, recovery_head, &rec,
1257                                    sizeof(rec), TDB1_DOCONV()) == -1) {
1258                 return true;
1259         }
1260
1261         return (rec.magic == TDB1_RECOVERY_MAGIC);
1262 }