1 /*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 1996, 1997, 1998 5 * Sleepycat Software. All rights reserved. 6 */ 7 8 #include "config.h" 9 10 #ifndef lint 11 static const char sccsid[] = "@(#)db_rec.c 10.19 (Sleepycat) 9/27/98"; 12 #endif /* not lint */ 13 14 #ifndef NO_SYSTEM_INCLUDES 15 #include <sys/types.h> 16 17 #include <string.h> 18 #endif 19 20 #include "db_int.h" 21 #include "shqueue.h" 22 #include "db_page.h" 23 #include "log.h" 24 #include "hash.h" 25 #include "btree.h" 26 27 /* 28 * PUBLIC: int __db_addrem_recover 29 * PUBLIC: __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 30 * 31 * This log message is generated whenever we add or remove a duplicate 32 * to/from a duplicate page. On recover, we just do the opposite. 33 */ 34 int 35 __db_addrem_recover(logp, dbtp, lsnp, redo, info) 36 DB_LOG *logp; 37 DBT *dbtp; 38 DB_LSN *lsnp; 39 int redo; 40 void *info; 41 { 42 __db_addrem_args *argp; 43 DB *file_dbp; 44 DBC *dbc; 45 DB_MPOOLFILE *mpf; 46 PAGE *pagep; 47 u_int32_t change; 48 int cmp_n, cmp_p, ret; 49 50 REC_PRINT(__db_addrem_print); 51 REC_INTRO(__db_addrem_read); 52 53 if ((ret = memp_fget(mpf, &argp->pgno, 0, &pagep)) != 0) { 54 if (!redo) { 55 /* 56 * We are undoing and the page doesn't exist. That 57 * is equivalent to having a pagelsn of 0, so we 58 * would not have to undo anything. In this case, 59 * don't bother creating a page. 60 */ 61 goto done; 62 } else 63 if ((ret = memp_fget(mpf, 64 &argp->pgno, DB_MPOOL_CREATE, &pagep)) != 0) 65 goto out; 66 } 67 68 cmp_n = log_compare(lsnp, &LSN(pagep)); 69 cmp_p = log_compare(&LSN(pagep), &argp->pagelsn); 70 change = 0; 71 if ((cmp_p == 0 && redo && argp->opcode == DB_ADD_DUP) || 72 (cmp_n == 0 && !redo && argp->opcode == DB_REM_DUP)) { 73 74 /* Need to redo an add, or undo a delete. */ 75 if ((ret = __db_pitem(dbc, pagep, argp->indx, argp->nbytes, 76 argp->hdr.size == 0 ? NULL : &argp->hdr, 77 argp->dbt.size == 0 ? NULL : &argp->dbt)) != 0) 78 goto out; 79 80 change = DB_MPOOL_DIRTY; 81 82 } else if ((cmp_n == 0 && !redo && argp->opcode == DB_ADD_DUP) || 83 (cmp_p == 0 && redo && argp->opcode == DB_REM_DUP)) { 84 /* Need to undo an add, or redo a delete. */ 85 if ((ret = __db_ditem(dbc, 86 pagep, argp->indx, argp->nbytes)) != 0) 87 goto out; 88 change = DB_MPOOL_DIRTY; 89 } 90 91 if (change) 92 if (redo) 93 LSN(pagep) = *lsnp; 94 else 95 LSN(pagep) = argp->pagelsn; 96 97 if ((ret = memp_fput(mpf, pagep, change)) != 0) 98 goto out; 99 100 done: *lsnp = argp->prev_lsn; 101 ret = 0; 102 103 out: REC_CLOSE; 104 } 105 106 /* 107 * PUBLIC: int __db_split_recover __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 108 */ 109 int 110 __db_split_recover(logp, dbtp, lsnp, redo, info) 111 DB_LOG *logp; 112 DBT *dbtp; 113 DB_LSN *lsnp; 114 int redo; 115 void *info; 116 { 117 __db_split_args *argp; 118 DB *file_dbp; 119 DBC *dbc; 120 DB_MPOOLFILE *mpf; 121 PAGE *pagep; 122 int change, cmp_n, cmp_p, ret; 123 124 REC_PRINT(__db_split_print); 125 REC_INTRO(__db_split_read); 126 127 if ((ret = memp_fget(mpf, &argp->pgno, 0, &pagep)) != 0) 128 if (!redo) { 129 /* 130 * We are undoing and the page doesn't exist. That 131 * is equivalent to having a pagelsn of 0, so we 132 * would not have to undo anything. In this case, 133 * don't bother creating a page. 134 */ 135 goto done; 136 } else 137 if ((ret = memp_fget(mpf, 138 &argp->pgno, DB_MPOOL_CREATE, &pagep)) != 0) 139 goto out; 140 141 /* 142 * There are two types of log messages here, one for the old page 143 * and one for the new pages created. The original image in the 144 * SPLITOLD record is used for undo. The image in the SPLITNEW 145 * is used for redo. We should never have a case where there is 146 * a redo operation and the SPLITOLD record is on disk, but not 147 * the SPLITNEW record. Therefore, we only redo NEW messages 148 * and only undo OLD messages. 149 */ 150 151 change = 0; 152 cmp_n = log_compare(lsnp, &LSN(pagep)); 153 cmp_p = log_compare(&LSN(pagep), &argp->pagelsn); 154 if (cmp_p == 0 && redo) { 155 if (argp->opcode == DB_SPLITNEW) { 156 /* Need to redo the split described. */ 157 memcpy(pagep, 158 argp->pageimage.data, argp->pageimage.size); 159 } 160 LSN(pagep) = *lsnp; 161 change = DB_MPOOL_DIRTY; 162 } else if (cmp_n == 0 && !redo) { 163 if (argp->opcode == DB_SPLITOLD) { 164 /* Put back the old image. */ 165 memcpy(pagep, 166 argp->pageimage.data, argp->pageimage.size); 167 } 168 LSN(pagep) = argp->pagelsn; 169 change = DB_MPOOL_DIRTY; 170 } 171 if ((ret = memp_fput(mpf, pagep, change)) != 0) 172 goto out; 173 174 done: *lsnp = argp->prev_lsn; 175 ret = 0; 176 177 out: REC_CLOSE; 178 } 179 180 /* 181 * PUBLIC: int __db_big_recover __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 182 */ 183 int 184 __db_big_recover(logp, dbtp, lsnp, redo, info) 185 DB_LOG *logp; 186 DBT *dbtp; 187 DB_LSN *lsnp; 188 int redo; 189 void *info; 190 { 191 __db_big_args *argp; 192 DB *file_dbp; 193 DBC *dbc; 194 DB_MPOOLFILE *mpf; 195 PAGE *pagep; 196 u_int32_t change; 197 int cmp_n, cmp_p, ret; 198 199 REC_PRINT(__db_big_print); 200 REC_INTRO(__db_big_read); 201 202 if ((ret = memp_fget(mpf, &argp->pgno, 0, &pagep)) != 0) { 203 if (!redo) { 204 /* 205 * We are undoing and the page doesn't exist. That 206 * is equivalent to having a pagelsn of 0, so we 207 * would not have to undo anything. In this case, 208 * don't bother creating a page. 209 */ 210 ret = 0; 211 goto ppage; 212 } else 213 if ((ret = memp_fget(mpf, 214 &argp->pgno, DB_MPOOL_CREATE, &pagep)) != 0) 215 goto out; 216 } 217 218 /* 219 * There are three pages we need to check. The one on which we are 220 * adding data, the previous one whose next_pointer may have 221 * been updated, and the next one whose prev_pointer may have 222 * been updated. 223 */ 224 cmp_n = log_compare(lsnp, &LSN(pagep)); 225 cmp_p = log_compare(&LSN(pagep), &argp->pagelsn); 226 change = 0; 227 if ((cmp_p == 0 && redo && argp->opcode == DB_ADD_BIG) || 228 (cmp_n == 0 && !redo && argp->opcode == DB_REM_BIG)) { 229 /* We are either redo-ing an add, or undoing a delete. */ 230 P_INIT(pagep, file_dbp->pgsize, argp->pgno, argp->prev_pgno, 231 argp->next_pgno, 0, P_OVERFLOW); 232 OV_LEN(pagep) = argp->dbt.size; 233 OV_REF(pagep) = 1; 234 memcpy((u_int8_t *)pagep + P_OVERHEAD, argp->dbt.data, 235 argp->dbt.size); 236 PREV_PGNO(pagep) = argp->prev_pgno; 237 change = DB_MPOOL_DIRTY; 238 } else if ((cmp_n == 0 && !redo && argp->opcode == DB_ADD_BIG) || 239 (cmp_p == 0 && redo && argp->opcode == DB_REM_BIG)) { 240 /* 241 * We are either undo-ing an add or redo-ing a delete. 242 * The page is about to be reclaimed in either case, so 243 * there really isn't anything to do here. 244 */ 245 change = DB_MPOOL_DIRTY; 246 } 247 if (change) 248 LSN(pagep) = redo ? *lsnp : argp->pagelsn; 249 250 if ((ret = memp_fput(mpf, pagep, change)) != 0) 251 goto out; 252 253 /* Now check the previous page. */ 254 ppage: if (argp->prev_pgno != PGNO_INVALID) { 255 change = 0; 256 if ((ret = memp_fget(mpf, &argp->prev_pgno, 0, &pagep)) != 0) 257 if (!redo) { 258 /* 259 * We are undoing and the page doesn't exist. 260 * That is equivalent to having a pagelsn of 0, 261 * so we would not have to undo anything. In 262 * this case, don't bother creating a page. 263 */ 264 *lsnp = argp->prev_lsn; 265 ret = 0; 266 goto npage; 267 } else 268 if ((ret = memp_fget(mpf, &argp->prev_pgno, 269 DB_MPOOL_CREATE, &pagep)) != 0) 270 goto out; 271 272 cmp_n = log_compare(lsnp, &LSN(pagep)); 273 cmp_p = log_compare(&LSN(pagep), &argp->prevlsn); 274 275 if ((cmp_p == 0 && redo && argp->opcode == DB_ADD_BIG) || 276 (cmp_n == 0 && !redo && argp->opcode == DB_REM_BIG)) { 277 /* Redo add, undo delete. */ 278 NEXT_PGNO(pagep) = argp->pgno; 279 change = DB_MPOOL_DIRTY; 280 } else if ((cmp_n == 0 && 281 !redo && argp->opcode == DB_ADD_BIG) || 282 (cmp_p == 0 && redo && argp->opcode == DB_REM_BIG)) { 283 /* Redo delete, undo add. */ 284 NEXT_PGNO(pagep) = argp->next_pgno; 285 change = DB_MPOOL_DIRTY; 286 } 287 if (change) 288 LSN(pagep) = redo ? *lsnp : argp->prevlsn; 289 if ((ret = memp_fput(mpf, pagep, change)) != 0) 290 goto out; 291 } 292 293 /* Now check the next page. Can only be set on a delete. */ 294 npage: if (argp->next_pgno != PGNO_INVALID) { 295 change = 0; 296 if ((ret = memp_fget(mpf, &argp->next_pgno, 0, &pagep)) != 0) 297 if (!redo) { 298 /* 299 * We are undoing and the page doesn't exist. 300 * That is equivalent to having a pagelsn of 0, 301 * so we would not have to undo anything. In 302 * this case, don't bother creating a page. 303 */ 304 goto done; 305 } else 306 if ((ret = memp_fget(mpf, &argp->next_pgno, 307 DB_MPOOL_CREATE, &pagep)) != 0) 308 goto out; 309 310 cmp_n = log_compare(lsnp, &LSN(pagep)); 311 cmp_p = log_compare(&LSN(pagep), &argp->nextlsn); 312 if (cmp_p == 0 && redo) { 313 PREV_PGNO(pagep) = PGNO_INVALID; 314 change = DB_MPOOL_DIRTY; 315 } else if (cmp_n == 0 && !redo) { 316 PREV_PGNO(pagep) = argp->pgno; 317 change = DB_MPOOL_DIRTY; 318 } 319 if (change) 320 LSN(pagep) = redo ? *lsnp : argp->nextlsn; 321 if ((ret = memp_fput(mpf, pagep, change)) != 0) 322 goto out; 323 } 324 325 done: *lsnp = argp->prev_lsn; 326 ret = 0; 327 328 out: REC_CLOSE; 329 } 330 331 /* 332 * __db_ovref_recover -- 333 * Recovery function for __db_ovref(). 334 * 335 * PUBLIC: int __db_ovref_recover __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 336 */ 337 int 338 __db_ovref_recover(logp, dbtp, lsnp, redo, info) 339 DB_LOG *logp; 340 DBT *dbtp; 341 DB_LSN *lsnp; 342 int redo; 343 void *info; 344 { 345 __db_ovref_args *argp; 346 DB *file_dbp; 347 DBC *dbc; 348 DB_MPOOLFILE *mpf; 349 PAGE *pagep; 350 int modified, ret; 351 352 REC_PRINT(__db_ovref_print); 353 REC_INTRO(__db_ovref_read); 354 355 if ((ret = memp_fget(mpf, &argp->pgno, 0, &pagep)) != 0) { 356 (void)__db_pgerr(file_dbp, argp->pgno); 357 goto out; 358 } 359 360 modified = 0; 361 if (log_compare(&LSN(pagep), &argp->lsn) == 0 && redo) { 362 /* Need to redo update described. */ 363 OV_REF(pagep) += argp->adjust; 364 365 pagep->lsn = *lsnp; 366 modified = 1; 367 } else if (log_compare(lsnp, &LSN(pagep)) == 0 && !redo) { 368 /* Need to undo update described. */ 369 OV_REF(pagep) -= argp->adjust; 370 371 pagep->lsn = argp->lsn; 372 modified = 1; 373 } 374 if ((ret = memp_fput(mpf, pagep, modified ? DB_MPOOL_DIRTY : 0)) != 0) 375 goto out; 376 377 done: *lsnp = argp->prev_lsn; 378 ret = 0; 379 380 out: REC_CLOSE; 381 } 382 383 /* 384 * __db_relink_recover -- 385 * Recovery function for relink. 386 * 387 * PUBLIC: int __db_relink_recover 388 * PUBLIC: __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 389 */ 390 int 391 __db_relink_recover(logp, dbtp, lsnp, redo, info) 392 DB_LOG *logp; 393 DBT *dbtp; 394 DB_LSN *lsnp; 395 int redo; 396 void *info; 397 { 398 __db_relink_args *argp; 399 DB *file_dbp; 400 DBC *dbc; 401 DB_MPOOLFILE *mpf; 402 PAGE *pagep; 403 int cmp_n, cmp_p, modified, ret; 404 405 REC_PRINT(__db_relink_print); 406 REC_INTRO(__db_relink_read); 407 408 /* 409 * There are up to three pages we need to check -- the page, and the 410 * previous and next pages, if they existed. For a page add operation, 411 * the current page is the result of a split and is being recovered 412 * elsewhere, so all we need do is recover the next page. 413 */ 414 if ((ret = memp_fget(mpf, &argp->pgno, 0, &pagep)) != 0) { 415 if (redo) { 416 (void)__db_pgerr(file_dbp, argp->pgno); 417 goto out; 418 } 419 goto next; 420 } 421 if (argp->opcode == DB_ADD_PAGE) 422 goto next; 423 424 modified = 0; 425 if (log_compare(&LSN(pagep), &argp->lsn) == 0 && redo) { 426 /* Redo the relink. */ 427 pagep->lsn = *lsnp; 428 modified = 1; 429 } else if (log_compare(lsnp, &LSN(pagep)) == 0 && !redo) { 430 /* Undo the relink. */ 431 pagep->next_pgno = argp->next; 432 pagep->prev_pgno = argp->prev; 433 434 pagep->lsn = argp->lsn; 435 modified = 1; 436 } 437 if ((ret = memp_fput(mpf, pagep, modified ? DB_MPOOL_DIRTY : 0)) != 0) 438 goto out; 439 440 next: if ((ret = memp_fget(mpf, &argp->next, 0, &pagep)) != 0) { 441 if (redo) { 442 (void)__db_pgerr(file_dbp, argp->next); 443 goto out; 444 } 445 goto prev; 446 } 447 modified = 0; 448 cmp_n = log_compare(lsnp, &LSN(pagep)); 449 cmp_p = log_compare(&LSN(pagep), &argp->lsn_next); 450 if ((argp->opcode == DB_REM_PAGE && cmp_p == 0 && redo) || 451 (argp->opcode == DB_ADD_PAGE && cmp_n == 0 && !redo)) { 452 /* Redo the remove or undo the add. */ 453 pagep->prev_pgno = argp->prev; 454 455 pagep->lsn = *lsnp; 456 modified = 1; 457 } else if ((argp->opcode == DB_REM_PAGE && cmp_n == 0 && !redo) || 458 (argp->opcode == DB_ADD_PAGE && cmp_p == 0 && redo)) { 459 /* Undo the remove or redo the add. */ 460 pagep->prev_pgno = argp->pgno; 461 462 pagep->lsn = argp->lsn_next; 463 modified = 1; 464 } 465 if ((ret = memp_fput(mpf, pagep, modified ? DB_MPOOL_DIRTY : 0)) != 0) 466 goto out; 467 if (argp->opcode == DB_ADD_PAGE) 468 goto done; 469 470 prev: if ((ret = memp_fget(mpf, &argp->prev, 0, &pagep)) != 0) { 471 if (redo) { 472 (void)__db_pgerr(file_dbp, argp->prev); 473 goto out; 474 } 475 goto done; 476 } 477 modified = 0; 478 if (log_compare(&LSN(pagep), &argp->lsn_prev) == 0 && redo) { 479 /* Redo the relink. */ 480 pagep->next_pgno = argp->next; 481 482 pagep->lsn = *lsnp; 483 modified = 1; 484 } else if (log_compare(lsnp, &LSN(pagep)) == 0 && !redo) { 485 /* Undo the relink. */ 486 pagep->next_pgno = argp->pgno; 487 488 pagep->lsn = argp->lsn_prev; 489 modified = 1; 490 } 491 if ((ret = memp_fput(mpf, pagep, modified ? DB_MPOOL_DIRTY : 0)) != 0) 492 goto out; 493 494 done: *lsnp = argp->prev_lsn; 495 ret = 0; 496 497 out: REC_CLOSE; 498 } 499 500 /* 501 * PUBLIC: int __db_addpage_recover 502 * PUBLIC: __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 503 */ 504 int 505 __db_addpage_recover(logp, dbtp, lsnp, redo, info) 506 DB_LOG *logp; 507 DBT *dbtp; 508 DB_LSN *lsnp; 509 int redo; 510 void *info; 511 { 512 __db_addpage_args *argp; 513 DB *file_dbp; 514 DBC *dbc; 515 DB_MPOOLFILE *mpf; 516 PAGE *pagep; 517 u_int32_t change; 518 int cmp_n, cmp_p, ret; 519 520 REC_PRINT(__db_addpage_print); 521 REC_INTRO(__db_addpage_read); 522 523 /* 524 * We need to check two pages: the old one and the new one onto 525 * which we're going to add duplicates. Do the old one first. 526 */ 527 if ((ret = memp_fget(mpf, &argp->pgno, 0, &pagep)) != 0) 528 goto out; 529 530 change = 0; 531 cmp_n = log_compare(lsnp, &LSN(pagep)); 532 cmp_p = log_compare(&LSN(pagep), &argp->lsn); 533 if (cmp_p == 0 && redo) { 534 NEXT_PGNO(pagep) = argp->nextpgno; 535 536 LSN(pagep) = *lsnp; 537 change = DB_MPOOL_DIRTY; 538 } else if (cmp_n == 0 && !redo) { 539 NEXT_PGNO(pagep) = PGNO_INVALID; 540 541 LSN(pagep) = argp->lsn; 542 change = DB_MPOOL_DIRTY; 543 } 544 if ((ret = memp_fput(mpf, pagep, change)) != 0) 545 goto out; 546 547 if ((ret = memp_fget(mpf, &argp->nextpgno, 0, &pagep)) != 0) 548 if (!redo) { 549 /* 550 * We are undoing and the page doesn't exist. That 551 * is equivalent to having a pagelsn of 0, so we 552 * would not have to undo anything. In this case, 553 * don't bother creating a page. 554 */ 555 goto done; 556 } else 557 if ((ret = memp_fget(mpf, 558 &argp->nextpgno, DB_MPOOL_CREATE, &pagep)) != 0) 559 goto out; 560 561 change = 0; 562 cmp_n = log_compare(lsnp, &LSN(pagep)); 563 cmp_p = log_compare(&LSN(pagep), &argp->nextlsn); 564 if (cmp_p == 0 && redo) { 565 PREV_PGNO(pagep) = argp->pgno; 566 567 LSN(pagep) = *lsnp; 568 change = DB_MPOOL_DIRTY; 569 } else if (cmp_n == 0 && !redo) { 570 PREV_PGNO(pagep) = PGNO_INVALID; 571 572 LSN(pagep) = argp->nextlsn; 573 change = DB_MPOOL_DIRTY; 574 } 575 if ((ret = memp_fput(mpf, pagep, change)) != 0) 576 goto out; 577 578 done: *lsnp = argp->prev_lsn; 579 ret = 0; 580 581 out: REC_CLOSE; 582 } 583 584 /* 585 * __db_debug_recover -- 586 * Recovery function for debug. 587 * 588 * PUBLIC: int __db_debug_recover __P((DB_LOG *, DBT *, DB_LSN *, int, void *)); 589 */ 590 int 591 __db_debug_recover(logp, dbtp, lsnp, redo, info) 592 DB_LOG *logp; 593 DBT *dbtp; 594 DB_LSN *lsnp; 595 int redo; 596 void *info; 597 { 598 __db_debug_args *argp; 599 int ret; 600 601 COMPQUIET(redo, 0); 602 COMPQUIET(logp, NULL); 603 604 REC_PRINT(__db_debug_print); 605 REC_NOOP_INTRO(__db_debug_read); 606 607 *lsnp = argp->prev_lsn; 608 ret = 0; 609 610 REC_NOOP_CLOSE; 611 } 612