1 /* Copyright (c) 2001-2016, The HSQL Development Group 2 * All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * Redistributions of source code must retain the above copyright notice, this 8 * list of conditions and the following disclaimer. 9 * 10 * Redistributions in binary form must reproduce the above copyright notice, main()11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * 14 * Neither the name of the HSQL Development Group nor the names of its 15 * contributors may be used to endorse or promote products derived from this 16 * software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG, 22 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 25 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 26 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 32 package org.hsqldb; 33 34 import org.hsqldb.error.Error; 35 import org.hsqldb.error.ErrorCode; 36 import org.hsqldb.lib.ArrayUtil; 37 import org.hsqldb.lib.OrderedHashSet; 38 import org.hsqldb.persist.PersistentStore; 39 40 /** 41 * Represents the chain of insert / delete / rollback / commit actions on a row. 42 * 43 * @author Fred Toussi (fredt@users dot sourceforge dot net) 44 * @version 2.3.3 45 * @since 2.0.0 46 */ 47 public class RowAction extends RowActionBase { 48 49 // 50 final TableBase table; 51 final PersistentStore store; 52 final Row memoryRow; 53 final long rowId; 54 boolean isMemory; 55 RowAction updatedAction; 56 57 public static RowAction addInsertAction(Session session, TableBase table, 58 Row row) { 59 60 RowAction action = new RowAction(session, table, ACTION_INSERT, row, 61 null); 62 63 row.rowAction = action; 64 65 return action; 66 } 67 68 public static RowAction addDeleteAction(Session session, TableBase table, 69 Row row, int[] colMap) { 70 71 RowAction action = row.rowAction; 72 73 if (action == null) { 74 action = new RowAction(session, table, ACTION_DELETE, row, colMap); 75 row.rowAction = action; 76 77 return action; 78 } 79 80 return action.addDeleteAction(session, colMap); 81 } 82 83 public static boolean addRefAction(Session session, Row row, 84 int[] colMap) { 85 86 RowAction action = row.rowAction; 87 88 if (action == null) { 89 action = new RowAction(session, row.getTable(), ACTION_REF, row, 90 colMap); 91 row.rowAction = action; 92 93 return true; 94 } 95 96 return action.addRefAction(session, colMap); 97 } 98 99 public RowAction(Session session, TableBase table, byte type, Row row, 100 int[] colMap) { 101 102 this.session = session; 103 this.type = type; 104 this.actionTimestamp = session.actionTimestamp; 105 this.table = table; 106 this.store = table.getRowStore(session); 107 this.isMemory = row.isMemory(); 108 this.memoryRow = row; 109 this.rowId = row.getPos(); 110 this.changeColumnMap = colMap; 111 } 112 113 private RowAction(RowAction other) { 114 115 this.session = other.session; 116 this.type = other.type; 117 this.actionTimestamp = other.actionTimestamp; 118 this.table = other.table; 119 this.store = other.store; 120 this.isMemory = other.isMemory; 121 this.memoryRow = other.memoryRow; 122 this.rowId = other.rowId; 123 this.changeColumnMap = other.changeColumnMap; 124 } 125 126 synchronized public int getType() { 127 return type; 128 } 129 130 synchronized RowAction addDeleteAction(Session session, int[] colMap) { 131 132 if (type == ACTION_NONE) { 133 setAsAction(session, ACTION_DELETE); 134 135 changeColumnMap = colMap; 136 } else { 137 RowActionBase action = this; 138 139 while (true) { 140 if (action.rolledback) { 141 if (action.next == null) { 142 break; 143 } 144 145 action = action.next; 146 147 continue; 148 } 149 150 switch (action.type) { 151 152 case ACTION_INSERT : { 153 if (action.commitTimestamp == 0 154 && session != action.session) { 155 throw Error.runtimeError(ErrorCode.U_S0500, 156 "RowAction"); 157 } 158 159 break; 160 } 161 case ACTION_DELETE_FINAL : 162 case ACTION_DELETE : { 163 if (session != action.session) { 164 if (action.commitTimestamp == 0) { 165 if (!session.actionSet.isEmpty()) { 166 session.actionSet.clear(); 167 } 168 169 session.actionSet.add(action); 170 } 171 172 return null; 173 } 174 175 break; 176 } 177 case ACTION_REF : { 178 if (session != action.session 179 && action.commitTimestamp == 0) { 180 if (colMap == null 181 || ArrayUtil.haveCommonElement( 182 colMap, action.changeColumnMap)) { 183 if (!session.actionSet.isEmpty()) { 184 session.actionSet.clear(); 185 } 186 187 session.actionSet.add(action); 188 189 return null; 190 } 191 } 192 193 break; 194 } 195 } 196 197 if (action.next == null) { 198 break; 199 } 200 201 action = action.next; 202 } 203 204 RowActionBase newAction = new RowActionBase(session, 205 ACTION_DELETE); 206 207 newAction.changeColumnMap = colMap; 208 action.next = newAction; 209 } 210 211 return this; 212 } 213 214 synchronized boolean addRefAction(Session session, int[] colMap) { 215 216 if (type == ACTION_NONE) { 217 setAsAction(session, ACTION_REF); 218 219 changeColumnMap = colMap; 220 221 return true; 222 } 223 224 RowActionBase action = this; 225 226 do { 227 if (session == action.session) { 228 if (action.type == ACTION_REF 229 && action.changeColumnMap == colMap 230 && action.commitTimestamp == 0) { 231 return false; 232 } 233 234 if (action.type == ACTION_INSERT) { 235 if (action.commitTimestamp == 0) { 236 return false; 237 } 238 } 239 } else { 240 if (action.type == ACTION_DELETE 241 && action.commitTimestamp == 0) { 242 if (action.changeColumnMap == null 243 || ArrayUtil.haveCommonElement( 244 colMap, action.changeColumnMap)) { 245 if (!session.actionSet.isEmpty()) { 246 session.actionSet.clear(); 247 } 248 249 session.actionSet.add(action); 250 251 return false; 252 } 253 } 254 } 255 256 if (action.next == null) { 257 break; 258 } 259 260 action = action.next; 261 } while (true); 262 263 RowActionBase newAction = new RowActionBase(session, ACTION_REF); 264 265 newAction.changeColumnMap = colMap; 266 action.next = newAction; 267 268 return true; 269 } 270 271 public boolean checkDeleteActions() { 272 return false; 273 } 274 275 public synchronized RowAction duplicate(Row newRow) { 276 277 RowAction action = new RowAction(session, table, type, newRow, 278 changeColumnMap); 279 280 return action; 281 } 282 283 synchronized void setAsAction(Session session, byte type) { 284 285 this.session = session; 286 this.type = type; 287 actionTimestamp = session.actionTimestamp; 288 changeColumnMap = null; 289 } 290 291 synchronized void setAsAction(RowActionBase action) { 292 super.setAsAction(action); 293 } 294 295 public void setAsNoOp() { 296 297 // memoryRow = null; 298 session = null; 299 actionTimestamp = 0; 300 commitTimestamp = 0; 301 rolledback = false; 302 deleteComplete = false; 303 changeColumnMap = null; 304 prepared = false; 305 type = ACTION_NONE; 306 next = null; 307 } 308 309 private void setAsDeleteFinal(long timestamp) { 310 311 actionTimestamp = 0; 312 commitTimestamp = timestamp; 313 rolledback = false; 314 deleteComplete = false; 315 prepared = false; 316 changeColumnMap = null; 317 type = ACTION_DELETE_FINAL; 318 next = null; 319 } 320 321 /** for two-phased pre-commit */ 322 synchronized void prepareCommit(Session session) { 323 324 RowActionBase action = this; 325 326 do { 327 if (action.session == session && action.commitTimestamp == 0) { 328 action.prepared = true; 329 } 330 331 action = action.next; 332 } while (action != null); 333 } 334 335 synchronized int commit(Session session) { 336 337 RowActionBase action = this; 338 int actiontype = ACTION_NONE; 339 340 do { 341 if (action.session == session && action.commitTimestamp == 0) { 342 action.commitTimestamp = session.actionTimestamp; 343 action.prepared = false; 344 345 if (action.type == ACTION_INSERT) { 346 actiontype = action.type; 347 } else if (action.type == ACTION_DELETE) { 348 if (actiontype == ACTION_INSERT) { 349 350 // ACTION_INSERT + ACTION_DELETE 351 actiontype = ACTION_INSERT_DELETE; 352 } else { 353 actiontype = action.type; 354 } 355 } 356 } 357 358 action = action.next; 359 } while (action != null); 360 361 return actiontype; 362 } 363 364 public boolean isDeleted() { 365 366 RowActionBase action = this; 367 368 do { 369 if (action.commitTimestamp != 0) { 370 if (action.type == ACTION_DELETE 371 || action.type == ACTION_DELETE_FINAL) { 372 return true; 373 } 374 } 375 376 action = action.next; 377 } while (action != null); 378 379 return false; 380 } 381 382 public boolean isDeleteComplete() { 383 return deleteComplete; 384 } 385 386 public void setDeleteComplete() { 387 deleteComplete = true; 388 } 389 390 /** 391 * returns type of commit performed on timestamp. ACTION_NONE if none. 392 * assumes rolled-back actions have already been merged 393 */ 394 synchronized int getCommitTypeOn(long timestamp) { 395 396 RowActionBase action = this; 397 int actionType = ACTION_NONE; 398 399 do { 400 if (action.commitTimestamp == timestamp) { 401 if (action.type == ACTION_INSERT) { 402 actionType = action.type; 403 } else if (action.type == ACTION_DELETE) { 404 if (actionType == ACTION_INSERT) { 405 406 // ACTION_INSERT + ACTION_DELETE 407 actionType = ACTION_INSERT_DELETE; 408 } else { 409 actionType = action.type; 410 } 411 } 412 } 413 414 action = action.next; 415 } while (action != null); 416 417 return actionType; 418 } 419 420 /** 421 * returns false if another committed session has altered the same row 422 */ 423 synchronized boolean canCommit(Session session, OrderedHashSet set) { 424 425 RowActionBase action; 426 long timestamp = session.transactionTimestamp; 427 long commitTimestamp = 0; 428 final boolean readCommitted = session.isolationLevel 429 == SessionInterface.TX_READ_COMMITTED; 430 boolean hasDelete = false; 431 432 action = this; 433 434 if (readCommitted) { 435 do { 436 if (action.session == session 437 && action.type == ACTION_DELETE) { 438 439 // for READ_COMMITTED, use action timestamp for later conflicts 440 if (action.commitTimestamp == 0) { 441 timestamp = action.actionTimestamp; 442 } 443 } 444 445 action = action.next; 446 } while (action != null); 447 448 action = this; 449 } 450 451 do { 452 if (action.session == session) { 453 if (action.type == ACTION_DELETE) { 454 hasDelete = true; 455 } 456 } else { 457 if (action.rolledback || action.type != ACTION_DELETE) { 458 action = action.next; 459 460 continue; 461 } 462 463 if (action.prepared) { 464 return false; 465 } 466 467 if (action.commitTimestamp == 0) { 468 set.add(action); 469 } else if (action.commitTimestamp > commitTimestamp) { 470 commitTimestamp = action.commitTimestamp; 471 } 472 } 473 474 action = action.next; 475 } while (action != null); 476 477 if (!hasDelete) { 478 return true; 479 } 480 481 return commitTimestamp < timestamp; 482 } 483 484 synchronized void complete(Session session) { 485 486 RowActionBase action; 487 488 action = this; 489 490 do { 491 if (action.session == session) { 492 if (action.actionTimestamp == 0) { 493 action.actionTimestamp = session.actionTimestamp; 494 } 495 } 496 497 action = action.next; 498 } while (action != null); 499 } 500 501 /** 502 * returns false if cannot complete 503 * when READ COMMITTED, false result always means repeat action and adds 504 * to set parameter the sessions to wait on (may be no wait) 505 */ 506 synchronized boolean complete(Session session, OrderedHashSet set) { 507 508 RowActionBase action; 509 boolean readCommitted = session.isolationLevel 510 == SessionInterface.TX_READ_COMMITTED; 511 boolean result = true; 512 513 action = this; 514 515 do { 516 if (action.rolledback || action.type == ACTION_NONE) { 517 action = action.next; 518 519 continue; 520 } 521 522 if (action.session == session) { 523 524 // 525 } else { 526 if (action.prepared) { 527 set.add(action.session); 528 529 return false; 530 } 531 532 if (readCommitted) { 533 if (action.commitTimestamp > session.actionTimestamp) { 534 535 // 2.0 -- investigate 536 // can redo - if deletes 537 // can redo - if dup, but will likely fail at retry 538 // can redo - if ref, but will likely fail at retry 539 set.add(session); 540 541 result = false; 542 } else if (action.commitTimestamp == 0) { 543 set.add(action.session); 544 545 result = false; 546 } 547 } else if (action.commitTimestamp 548 > session.transactionTimestamp) { 549 return false; 550 } 551 } 552 553 action = action.next; 554 } while (action != null); 555 556 return result; 557 } 558 559 public long getPos() { 560 return rowId; 561 } 562 563 public Row getRow() { 564 return memoryRow; 565 } 566 567 private int getRollbackType(Session session) { 568 569 int actionType = ACTION_NONE; 570 RowActionBase action = this; 571 572 do { 573 if (action.session == session && action.rolledback) { 574 if (action.type == ACTION_DELETE) { 575 if (actionType == ACTION_INSERT) { 576 actionType = ACTION_INSERT_DELETE; 577 } else { 578 actionType = action.type; 579 } 580 } else if (action.type == ACTION_INSERT) { 581 actionType = action.type; 582 } 583 } 584 585 action = action.next; 586 } while (action != null); 587 588 return actionType; 589 } 590 591 /** 592 * Rollback actions for a session including and after the given timestamp 593 */ 594 synchronized void rollback(Session session, long timestamp) { 595 596 RowActionBase action = this; 597 598 do { 599 if (action.session == session && action.commitTimestamp == 0) { 600 if (action.actionTimestamp >= timestamp) { 601 action.commitTimestamp = session.actionTimestamp; 602 action.rolledback = true; 603 action.prepared = false; 604 } 605 } 606 607 action = action.next; 608 } while (action != null); 609 } 610 611 /** 612 * merge rolled back actions 613 */ 614 synchronized int mergeRollback(Session session, long timestamp, Row row) { 615 616 RowActionBase action = this; 617 RowActionBase head = null; 618 RowActionBase tail = null; 619 int rollbackAction = getRollbackType(session); 620 621 do { 622 if (action.session == session && action.rolledback) { 623 if (tail != null) { 624 tail.next = null; 625 } 626 } else { 627 if (head == null) { 628 head = tail = action; 629 } else { 630 tail.next = action; 631 tail = action; 632 } 633 } 634 635 action = action.next; 636 } while (action != null); 637 638 if (head == null) { 639 switch (rollbackAction) { 640 641 case ACTION_INSERT : 642 case ACTION_INSERT_DELETE : 643 setAsDeleteFinal(timestamp); 644 break; 645 646 case ACTION_DELETE : 647 case ACTION_NONE : 648 default : 649 setAsNoOp(); 650 break; 651 } 652 } else { 653 if (head != this) { 654 setAsAction(head); 655 } 656 } 657 658 return rollbackAction; 659 } 660 661 /** 662 * merge session actions committed on given timestamp. 663 * 664 * may be called more than once on same action 665 * 666 */ 667 synchronized void mergeToTimestamp(long timestamp) { 668 669 RowActionBase action = this; 670 RowActionBase head = null; 671 RowActionBase tail = null; 672 int commitType = getCommitTypeOn(timestamp); 673 674 if (type == ACTION_DELETE_FINAL || type == ACTION_NONE) { 675 return; 676 } 677 678 if (commitType == ACTION_DELETE 679 || commitType == ACTION_INSERT_DELETE) { 680 setAsDeleteFinal(timestamp); 681 682 return; 683 } 684 685 do { 686 boolean expired = false; 687 688 if (action.commitTimestamp != 0) { 689 if (action.commitTimestamp <= timestamp) { 690 expired = true; 691 } else if (action.type == ACTION_REF) { 692 expired = true; 693 } 694 } 695 696 if (expired) { 697 if (tail != null) { 698 tail.next = null; 699 } 700 } else { 701 if (head == null) { 702 head = tail = action; 703 } else { 704 tail.next = action; 705 tail = action; 706 } 707 } 708 709 action = action.next; 710 } while (action != null); 711 712 if (head == null) { 713 switch (commitType) { 714 715 case ACTION_DELETE : 716 case ACTION_INSERT_DELETE : 717 setAsDeleteFinal(timestamp); 718 break; 719 720 case ACTION_NONE : 721 case ACTION_INSERT : 722 default : 723 setAsNoOp(); 724 break; 725 } 726 } else if (head != this) { 727 setAsAction(head); 728 } 729 730 mergeExpiredRefActions(); 731 } 732 733 public synchronized boolean canRead(Session session, int mode) { 734 735 long threshold; 736 int actionType = ACTION_NONE; 737 738 if (type == ACTION_DELETE_FINAL) { 739 return false; 740 } 741 742 if (type == ACTION_NONE) { 743 return true; 744 } 745 746 RowActionBase action = this; 747 748 if (session == null) { 749 threshold = Long.MAX_VALUE; 750 } else { 751 switch (session.isolationLevel) { 752 753 case SessionInterface.TX_READ_UNCOMMITTED : 754 threshold = Long.MAX_VALUE; 755 break; 756 757 case SessionInterface.TX_READ_COMMITTED : 758 threshold = session.actionTimestamp; 759 break; 760 761 case SessionInterface.TX_REPEATABLE_READ : 762 case SessionInterface.TX_SERIALIZABLE : 763 default : 764 threshold = session.transactionTimestamp; 765 break; 766 } 767 } 768 769 do { 770 if (action.type == ACTION_REF) { 771 action = action.next; 772 773 continue; 774 } 775 776 if (action.rolledback) { 777 if (action.type == ACTION_INSERT) { 778 actionType = ACTION_DELETE; 779 } 780 781 action = action.next; 782 783 continue; 784 } 785 786 if (session == action.session) { 787 if (action.type == ACTION_DELETE) { 788 actionType = action.type; 789 } else if (action.type == ACTION_INSERT) { 790 actionType = action.type; 791 } 792 793 action = action.next; 794 795 continue; 796 } else if (action.commitTimestamp == 0) { 797 if (action.type == ACTION_NONE) { 798 throw Error.runtimeError(ErrorCode.U_S0500, "RowAction"); 799 } else if (action.type == ACTION_INSERT) { 800 if (mode == TransactionManager.ACTION_READ) { 801 actionType = ACTION_DELETE; 802 } else if (mode == TransactionManager.ACTION_DUP) { 803 actionType = ACTION_INSERT; 804 805 session.actionSet.clear(); 806 session.actionSet.add(action); 807 } else if (mode == TransactionManager.ACTION_REF) { 808 actionType = ACTION_DELETE; 809 } 810 811 break; 812 } else if (action.type == ACTION_DELETE) { 813 if (mode == TransactionManager.ACTION_DUP) { 814 815 // 816 } else if (mode == TransactionManager.ACTION_REF) { 817 actionType = ACTION_DELETE; 818 } 819 } 820 821 action = action.next; 822 823 continue; 824 } else if (action.commitTimestamp < threshold) { 825 if (action.type == ACTION_DELETE) { 826 actionType = ACTION_DELETE; 827 } else if (action.type == ACTION_INSERT) { 828 actionType = ACTION_INSERT; 829 } 830 } else { 831 if (action.type == ACTION_INSERT) { 832 if (mode == TransactionManager.ACTION_READ) { 833 actionType = ACTION_DELETE; 834 } else if (mode == TransactionManager.ACTION_DUP) { 835 actionType = ACTION_INSERT; 836 837 session.actionSet.clear(); 838 session.actionSet.add(action); 839 } else if (mode == TransactionManager.ACTION_REF) { 840 actionType = ACTION_DELETE; 841 } 842 } 843 } 844 845 action = action.next; 846 847 continue; 848 } while (action != null); 849 850 if (actionType == ACTION_NONE || actionType == ACTION_INSERT) { 851 return true; 852 } 853 854 return false; 855 } 856 857 public boolean hasCurrentRefAction() { 858 859 RowActionBase action = this; 860 861 do { 862 if (action.type == ACTION_REF && action.commitTimestamp == 0) { 863 return true; 864 } 865 866 action = action.next; 867 } while (action != null); 868 869 return false; 870 } 871 872 /** eliminate all expired updatedAction in chain */ 873 private RowAction mergeExpiredRefActions() { 874 875 if (updatedAction != null) { 876 updatedAction = updatedAction.mergeExpiredRefActions(); 877 } 878 879 if (hasCurrentRefAction()) { 880 return this; 881 } 882 883 return updatedAction; 884 } 885 886 public synchronized String describe(Session session) { 887 888 StringBuilder sb = new StringBuilder(); 889 RowActionBase action = this; 890 891 do { 892 if (action == this) { 893 sb.append(this.rowId).append(' '); 894 } 895 896 sb.append(action.session.getId()).append(' '); 897 sb.append(action.type).append(' ').append(action.actionTimestamp); 898 sb.append(' ').append(action.commitTimestamp); 899 900 if (action.commitTimestamp != 0) { 901 if (action.rolledback) { 902 sb.append('r'); 903 } else { 904 sb.append('c'); 905 } 906 } 907 908 sb.append(" - "); 909 910 action = action.next; 911 } while (action != null); 912 913 return sb.toString(); 914 } 915 } 916