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