release/src/router/mysql/storage/innobase/fut/fut0lst.c

   1 /**********************************************************************
   2 File-based list utilities
   3
   4 (c) 1995 Innobase Oy
   5
   6 Created 11/28/1995 Heikki Tuuri
   7 ***********************************************************************/
   8
   9 #include "fut0lst.h"
  10
  11 #ifdef UNIV_NONINL
  12 #include "fut0lst.ic"
  13 #endif
  14
  15 #include "buf0buf.h"
  16
  17
  18 /************************************************************************
  19 Adds a node to an empty list. */
  20 static
  21 void
  22 flst_add_to_empty(
  23 /*==============*/
  24         flst_base_node_t*       base,   /* in: pointer to base node of
  25                                         empty list */
  26         flst_node_t*            node,   /* in: node to add */
  27         mtr_t*                  mtr)    /* in: mini-transaction handle */
  28 {
  29         ulint           space;
  30         fil_addr_t      node_addr;
  31         ulint           len;
  32
  33         ut_ad(mtr && base && node);
  34         ut_ad(base != node);
  35         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
  36                                 MTR_MEMO_PAGE_X_FIX));
  37         ut_ad(mtr_memo_contains(mtr, buf_block_align(node),
  38                                 MTR_MEMO_PAGE_X_FIX));
  39         len = flst_get_len(base, mtr);
  40         ut_a(len == 0);
  41
  42         buf_ptr_get_fsp_addr(node, &space, &node_addr);
  43
  44         /* Update first and last fields of base node */
  45         flst_write_addr(base + FLST_FIRST, node_addr, mtr);
  46         flst_write_addr(base + FLST_LAST, node_addr, mtr);
  47
  48         /* Set prev and next fields of node to add */
  49         flst_write_addr(node + FLST_PREV, fil_addr_null, mtr);
  50         flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr);
  51
  52         /* Update len of base node */
  53         mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
  54 }
  55
  56 /************************************************************************
  57 Adds a node as the last node in a list. */
  58
  59 void
  60 flst_add_last(
  61 /*==========*/
  62         flst_base_node_t*       base,   /* in: pointer to base node of list */
  63         flst_node_t*            node,   /* in: node to add */
  64         mtr_t*                  mtr)    /* in: mini-transaction handle */
  65 {
  66         ulint           space;
  67         fil_addr_t      node_addr;
  68         ulint           len;
  69         fil_addr_t      last_addr;
  70         flst_node_t*    last_node;
  71
  72         ut_ad(mtr && base && node);
  73         ut_ad(base != node);
  74         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
  75                                 MTR_MEMO_PAGE_X_FIX));
  76         ut_ad(mtr_memo_contains(mtr, buf_block_align(node),
  77                                 MTR_MEMO_PAGE_X_FIX));
  78         len = flst_get_len(base, mtr);
  79         last_addr = flst_get_last(base, mtr);
  80
  81         buf_ptr_get_fsp_addr(node, &space, &node_addr);
  82
  83         /* If the list is not empty, call flst_insert_after */
  84         if (len != 0) {
  85                 if (last_addr.page == node_addr.page) {
  86                         last_node = buf_frame_align(node) + last_addr.boffset;
  87                 } else {
  88                         last_node = fut_get_ptr(space, last_addr, RW_X_LATCH,
  89                                                 mtr);
  90                 }
  91
  92                 flst_insert_after(base, last_node, node, mtr);
  93         } else {
  94                 /* else call flst_add_to_empty */
  95                 flst_add_to_empty(base, node, mtr);
  96         }
  97 }
  98
  99 /************************************************************************
 100 Adds a node as the first node in a list. */
 101
 102 void
 103 flst_add_first(
 104 /*===========*/
 105         flst_base_node_t*       base,   /* in: pointer to base node of list */
 106         flst_node_t*            node,   /* in: node to add */
 107         mtr_t*                  mtr)    /* in: mini-transaction handle */
 108 {
 109         ulint           space;
 110         fil_addr_t      node_addr;
 111         ulint           len;
 112         fil_addr_t      first_addr;
 113         flst_node_t*    first_node;
 114
 115         ut_ad(mtr && base && node);
 116         ut_ad(base != node);
 117         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 118                                 MTR_MEMO_PAGE_X_FIX));
 119         ut_ad(mtr_memo_contains(mtr, buf_block_align(node),
 120                                 MTR_MEMO_PAGE_X_FIX));
 121         len = flst_get_len(base, mtr);
 122         first_addr = flst_get_first(base, mtr);
 123
 124         buf_ptr_get_fsp_addr(node, &space, &node_addr);
 125
 126         /* If the list is not empty, call flst_insert_before */
 127         if (len != 0) {
 128                 if (first_addr.page == node_addr.page) {
 129                         first_node = buf_frame_align(node)
 130                                 + first_addr.boffset;
 131                 } else {
 132                         first_node = fut_get_ptr(space, first_addr,
 133                                                  RW_X_LATCH, mtr);
 134                 }
 135
 136                 flst_insert_before(base, node, first_node, mtr);
 137         } else {
 138                 /* else call flst_add_to_empty */
 139                 flst_add_to_empty(base, node, mtr);
 140         }
 141 }
 142
 143 /************************************************************************
 144 Inserts a node after another in a list. */
 145
 146 void
 147 flst_insert_after(
 148 /*==============*/
 149         flst_base_node_t*       base,   /* in: pointer to base node of list */
 150         flst_node_t*            node1,  /* in: node to insert after */
 151         flst_node_t*            node2,  /* in: node to add */
 152         mtr_t*                  mtr)    /* in: mini-transaction handle */
 153 {
 154         ulint           space;
 155         fil_addr_t      node1_addr;
 156         fil_addr_t      node2_addr;
 157         flst_node_t*    node3;
 158         fil_addr_t      node3_addr;
 159         ulint           len;
 160
 161         ut_ad(mtr && node1 && node2 && base);
 162         ut_ad(base != node1);
 163         ut_ad(base != node2);
 164         ut_ad(node2 != node1);
 165         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 166                                 MTR_MEMO_PAGE_X_FIX));
 167         ut_ad(mtr_memo_contains(mtr, buf_block_align(node1),
 168                                 MTR_MEMO_PAGE_X_FIX));
 169         ut_ad(mtr_memo_contains(mtr, buf_block_align(node2),
 170                                 MTR_MEMO_PAGE_X_FIX));
 171
 172         buf_ptr_get_fsp_addr(node1, &space, &node1_addr);
 173         buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 174
 175         node3_addr = flst_get_next_addr(node1, mtr);
 176
 177         /* Set prev and next fields of node2 */
 178         flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
 179         flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
 180
 181         if (!fil_addr_is_null(node3_addr)) {
 182                 /* Update prev field of node3 */
 183                 node3 = fut_get_ptr(space, node3_addr, RW_X_LATCH, mtr);
 184                 flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
 185         } else {
 186                 /* node1 was last in list: update last field in base */
 187                 flst_write_addr(base + FLST_LAST, node2_addr, mtr);
 188         }
 189
 190         /* Set next field of node1 */
 191         flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
 192
 193         /* Update len of base node */
 194         len = flst_get_len(base, mtr);
 195         mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
 196 }
 197
 198 /************************************************************************
 199 Inserts a node before another in a list. */
 200
 201 void
 202 flst_insert_before(
 203 /*===============*/
 204         flst_base_node_t*       base,   /* in: pointer to base node of list */
 205         flst_node_t*            node2,  /* in: node to insert */
 206         flst_node_t*            node3,  /* in: node to insert before */
 207         mtr_t*                  mtr)    /* in: mini-transaction handle */
 208 {
 209         ulint           space;
 210         flst_node_t*    node1;
 211         fil_addr_t      node1_addr;
 212         fil_addr_t      node2_addr;
 213         fil_addr_t      node3_addr;
 214         ulint           len;
 215
 216         ut_ad(mtr && node2 && node3 && base);
 217         ut_ad(base != node2);
 218         ut_ad(base != node3);
 219         ut_ad(node2 != node3);
 220         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 221                                 MTR_MEMO_PAGE_X_FIX));
 222         ut_ad(mtr_memo_contains(mtr, buf_block_align(node2),
 223                                 MTR_MEMO_PAGE_X_FIX));
 224         ut_ad(mtr_memo_contains(mtr, buf_block_align(node3),
 225                                 MTR_MEMO_PAGE_X_FIX));
 226
 227         buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 228         buf_ptr_get_fsp_addr(node3, &space, &node3_addr);
 229
 230         node1_addr = flst_get_prev_addr(node3, mtr);
 231
 232         /* Set prev and next fields of node2 */
 233         flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
 234         flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
 235
 236         if (!fil_addr_is_null(node1_addr)) {
 237                 /* Update next field of node1 */
 238                 node1 = fut_get_ptr(space, node1_addr, RW_X_LATCH, mtr);
 239                 flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
 240         } else {
 241                 /* node3 was first in list: update first field in base */
 242                 flst_write_addr(base + FLST_FIRST, node2_addr, mtr);
 243         }
 244
 245         /* Set prev field of node3 */
 246         flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
 247
 248         /* Update len of base node */
 249         len = flst_get_len(base, mtr);
 250         mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
 251 }
 252
 253 /************************************************************************
 254 Removes a node. */
 255
 256 void
 257 flst_remove(
 258 /*========*/
 259         flst_base_node_t*       base,   /* in: pointer to base node of list */
 260         flst_node_t*            node2,  /* in: node to remove */
 261         mtr_t*                  mtr)    /* in: mini-transaction handle */
 262 {
 263         ulint           space;
 264         flst_node_t*    node1;
 265         fil_addr_t      node1_addr;
 266         fil_addr_t      node2_addr;
 267         flst_node_t*    node3;
 268         fil_addr_t      node3_addr;
 269         ulint           len;
 270
 271         ut_ad(mtr && node2 && base);
 272         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 273                                 MTR_MEMO_PAGE_X_FIX));
 274         ut_ad(mtr_memo_contains(mtr, buf_block_align(node2),
 275                                 MTR_MEMO_PAGE_X_FIX));
 276
 277         buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 278
 279         node1_addr = flst_get_prev_addr(node2, mtr);
 280         node3_addr = flst_get_next_addr(node2, mtr);
 281
 282         if (!fil_addr_is_null(node1_addr)) {
 283
 284                 /* Update next field of node1 */
 285
 286                 if (node1_addr.page == node2_addr.page) {
 287
 288                         node1 = buf_frame_align(node2) + node1_addr.boffset;
 289                 } else {
 290                         node1 = fut_get_ptr(space, node1_addr, RW_X_LATCH,
 291                                             mtr);
 292                 }
 293
 294                 ut_ad(node1 != node2);
 295
 296                 flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr);
 297         } else {
 298                 /* node2 was first in list: update first field in base */
 299                 flst_write_addr(base + FLST_FIRST, node3_addr, mtr);
 300         }
 301
 302         if (!fil_addr_is_null(node3_addr)) {
 303                 /* Update prev field of node3 */
 304
 305                 if (node3_addr.page == node2_addr.page) {
 306
 307                         node3 = buf_frame_align(node2) + node3_addr.boffset;
 308                 } else {
 309                         node3 = fut_get_ptr(space, node3_addr, RW_X_LATCH,
 310                                             mtr);
 311                 }
 312
 313                 ut_ad(node2 != node3);
 314
 315                 flst_write_addr(node3 + FLST_PREV, node1_addr, mtr);
 316         } else {
 317                 /* node2 was last in list: update last field in base */
 318                 flst_write_addr(base + FLST_LAST, node1_addr, mtr);
 319         }
 320
 321         /* Update len of base node */
 322         len = flst_get_len(base, mtr);
 323         ut_ad(len > 0);
 324
 325         mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr);
 326 }
 327
 328 /************************************************************************
 329 Cuts off the tail of the list, including the node given. The number of
 330 nodes which will be removed must be provided by the caller, as this function
 331 does not measure the length of the tail. */
 332
 333 void
 334 flst_cut_end(
 335 /*=========*/
 336         flst_base_node_t*       base,   /* in: pointer to base node of list */
 337         flst_node_t*            node2,  /* in: first node to remove */
 338         ulint                   n_nodes,/* in: number of nodes to remove,
 339                                         must be >= 1 */
 340         mtr_t*                  mtr)    /* in: mini-transaction handle */
 341 {
 342         ulint           space;
 343         flst_node_t*    node1;
 344         fil_addr_t      node1_addr;
 345         fil_addr_t      node2_addr;
 346         ulint           len;
 347
 348         ut_ad(mtr && node2 && base);
 349         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 350                                 MTR_MEMO_PAGE_X_FIX));
 351         ut_ad(mtr_memo_contains(mtr, buf_block_align(node2),
 352                                 MTR_MEMO_PAGE_X_FIX));
 353         ut_ad(n_nodes > 0);
 354
 355         buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 356
 357         node1_addr = flst_get_prev_addr(node2, mtr);
 358
 359         if (!fil_addr_is_null(node1_addr)) {
 360
 361                 /* Update next field of node1 */
 362
 363                 if (node1_addr.page == node2_addr.page) {
 364
 365                         node1 = buf_frame_align(node2) + node1_addr.boffset;
 366                 } else {
 367                         node1 = fut_get_ptr(space, node1_addr, RW_X_LATCH,
 368                                             mtr);
 369                 }
 370
 371                 flst_write_addr(node1 + FLST_NEXT, fil_addr_null, mtr);
 372         } else {
 373                 /* node2 was first in list: update the field in base */
 374                 flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr);
 375         }
 376
 377         flst_write_addr(base + FLST_LAST, node1_addr, mtr);
 378
 379         /* Update len of base node */
 380         len = flst_get_len(base, mtr);
 381         ut_ad(len >= n_nodes);
 382
 383         mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
 384 }
 385
 386 /************************************************************************
 387 Cuts off the tail of the list, not including the given node. The number of
 388 nodes which will be removed must be provided by the caller, as this function
 389 does not measure the length of the tail. */
 390
 391 void
 392 flst_truncate_end(
 393 /*==============*/
 394         flst_base_node_t*       base,   /* in: pointer to base node of list */
 395         flst_node_t*            node2,  /* in: first node not to remove */
 396         ulint                   n_nodes,/* in: number of nodes to remove */
 397         mtr_t*                  mtr)    /* in: mini-transaction handle */
 398 {
 399         fil_addr_t      node2_addr;
 400         ulint           len;
 401         ulint           space;
 402
 403         ut_ad(mtr && node2 && base);
 404         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 405                                 MTR_MEMO_PAGE_X_FIX));
 406         ut_ad(mtr_memo_contains(mtr, buf_block_align(node2),
 407                                 MTR_MEMO_PAGE_X_FIX));
 408         if (n_nodes == 0) {
 409
 410                 ut_ad(fil_addr_is_null(flst_get_next_addr(node2, mtr)));
 411
 412                 return;
 413         }
 414
 415         buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 416
 417         /* Update next field of node2 */
 418         flst_write_addr(node2 + FLST_NEXT, fil_addr_null, mtr);
 419
 420         flst_write_addr(base + FLST_LAST, node2_addr, mtr);
 421
 422         /* Update len of base node */
 423         len = flst_get_len(base, mtr);
 424         ut_ad(len >= n_nodes);
 425
 426         mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
 427 }
 428
 429 /************************************************************************
 430 Validates a file-based list. */
 431
 432 ibool
 433 flst_validate(
 434 /*==========*/
 435                                         /* out: TRUE if ok */
 436         flst_base_node_t*       base,   /* in: pointer to base node of list */
 437         mtr_t*                  mtr1)   /* in: mtr */
 438 {
 439         ulint           space;
 440         flst_node_t*    node;
 441         fil_addr_t      node_addr;
 442         fil_addr_t      base_addr;
 443         ulint           len;
 444         ulint           i;
 445         mtr_t           mtr2;
 446
 447         ut_ad(base);
 448         ut_ad(mtr_memo_contains(mtr1, buf_block_align(base),
 449                                 MTR_MEMO_PAGE_X_FIX));
 450
 451         /* We use two mini-transaction handles: the first is used to
 452         lock the base node, and prevent other threads from modifying the
 453         list. The second is used to traverse the list. We cannot run the
 454         second mtr without committing it at times, because if the list
 455         is long, then the x-locked pages could fill the buffer resulting
 456         in a deadlock. */
 457
 458         /* Find out the space id */
 459         buf_ptr_get_fsp_addr(base, &space, &base_addr);
 460
 461         len = flst_get_len(base, mtr1);
 462         node_addr = flst_get_first(base, mtr1);
 463
 464         for (i = 0; i < len; i++) {
 465                 mtr_start(&mtr2);
 466
 467                 node = fut_get_ptr(space, node_addr, RW_X_LATCH, &mtr2);
 468                 node_addr = flst_get_next_addr(node, &mtr2);
 469
 470                 mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
 471                                    becoming full */
 472         }
 473
 474         ut_a(fil_addr_is_null(node_addr));
 475
 476         node_addr = flst_get_last(base, mtr1);
 477
 478         for (i = 0; i < len; i++) {
 479                 mtr_start(&mtr2);
 480
 481                 node = fut_get_ptr(space, node_addr, RW_X_LATCH, &mtr2);
 482                 node_addr = flst_get_prev_addr(node, &mtr2);
 483
 484                 mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
 485                                    becoming full */
 486         }
 487
 488         ut_a(fil_addr_is_null(node_addr));
 489
 490         return(TRUE);
 491 }
 492
 493 /************************************************************************
 494 Prints info of a file-based list. */
 495
 496 void
 497 flst_print(
 498 /*=======*/
 499         flst_base_node_t*       base,   /* in: pointer to base node of list */
 500         mtr_t*                  mtr)    /* in: mtr */
 501 {
 502         buf_frame_t*    frame;
 503         ulint           len;
 504
 505         ut_ad(base && mtr);
 506         ut_ad(mtr_memo_contains(mtr, buf_block_align(base),
 507                                 MTR_MEMO_PAGE_X_FIX));
 508         frame = buf_frame_align(base);
 509
 510         len = flst_get_len(base, mtr);
 511
 512         fprintf(stderr,
 513                 "FILE-BASED LIST:\n"
 514                 "Base node in space %lu page %lu byte offset %lu; len %lu\n",
 515                 (ulong) buf_frame_get_space_id(frame),
 516                 (ulong) buf_frame_get_page_no(frame),
 517                 (ulong) (base - frame), (ulong) len);
 518 }