Dbtux.hpp 32.3 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
/* Copyright (C) 2003 MySQL AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

#ifndef DBTUX_H
#define DBTUX_H

#include <ndb_limits.h>
#include <SimulatedBlock.hpp>
22
#include <AttributeDescriptor.hpp>
23 24 25 26 27
#include <AttributeHeader.hpp>
#include <ArrayPool.hpp>
#include <DataBuffer.hpp>
#include <md5_hash.hpp>

28 29 30
// big brother
#include <Dbtup.hpp>

31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
// signal classes
#include <signaldata/DictTabInfo.hpp>
#include <signaldata/TuxContinueB.hpp>
#include <signaldata/TupFrag.hpp>
#include <signaldata/AlterIndx.hpp>
#include <signaldata/DropTab.hpp>
#include <signaldata/TuxMaint.hpp>
#include <signaldata/AccScan.hpp>
#include <signaldata/TuxBound.hpp>
#include <signaldata/NextScan.hpp>
#include <signaldata/AccLock.hpp>
#include <signaldata/DumpStateOrd.hpp>

// debug
#ifdef VM_TRACE
#include <NdbOut.hpp>
#include <OutputStream.hpp>
#endif

// jams
#undef jam
#undef jamEntry
#ifdef DBTUX_GEN_CPP
#define jam()           jamLine(10000 + __LINE__)
#define jamEntry()      jamEntryLine(10000 + __LINE__)
#endif
#ifdef DBTUX_META_CPP
#define jam()           jamLine(20000 + __LINE__)
#define jamEntry()      jamEntryLine(20000 + __LINE__)
#endif
#ifdef DBTUX_MAINT_CPP
#define jam()           jamLine(30000 + __LINE__)
#define jamEntry()      jamEntryLine(30000 + __LINE__)
#endif
#ifdef DBTUX_NODE_CPP
#define jam()           jamLine(40000 + __LINE__)
#define jamEntry()      jamEntryLine(40000 + __LINE__)
#endif
#ifdef DBTUX_TREE_CPP
#define jam()           jamLine(50000 + __LINE__)
#define jamEntry()      jamEntryLine(50000 + __LINE__)
#endif
#ifdef DBTUX_SCAN_CPP
#define jam()           jamLine(60000 + __LINE__)
#define jamEntry()      jamEntryLine(60000 + __LINE__)
#endif
77
#ifdef DBTUX_SEARCH_CPP
78 79 80
#define jam()           jamLine(70000 + __LINE__)
#define jamEntry()      jamEntryLine(70000 + __LINE__)
#endif
81 82 83 84
#ifdef DBTUX_CMP_CPP
#define jam()           jamLine(80000 + __LINE__)
#define jamEntry()      jamEntryLine(80000 + __LINE__)
#endif
85 86 87 88
#ifdef DBTUX_DEBUG_CPP
#define jam()           jamLine(90000 + __LINE__)
#define jamEntry()      jamEntryLine(90000 + __LINE__)
#endif
89 90 91 92
#ifndef jam
#define jam()           jamLine(__LINE__)
#define jamEntry()      jamEntryLine(__LINE__)
#endif
93

tomas@mc05.(none)'s avatar
tomas@mc05.(none) committed
94 95 96
#undef max
#undef min

97 98 99 100 101 102 103
class Configuration;

class Dbtux : public SimulatedBlock {
public:
  Dbtux(const Configuration& conf);
  virtual ~Dbtux();

104 105 106
  // pointer to TUP instance in this thread
  Dbtup* c_tup;

107 108
private:
  // sizes are in words (Uint32)
109 110 111
  STATIC_CONST( MaxIndexFragments = 2 * MAX_FRAG_PER_NODE );
  STATIC_CONST( MaxIndexAttributes = MAX_ATTRIBUTES_IN_INDEX );
  STATIC_CONST( MaxAttrDataSize = 2048 );
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
112
public:
113
  STATIC_CONST( DescPageSize = 256 );
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
114
private:
115 116 117 118
  STATIC_CONST( MaxTreeNodeSize = MAX_TTREE_NODE_SIZE );
  STATIC_CONST( MaxPrefSize = MAX_TTREE_PREF_SIZE );
  STATIC_CONST( ScanBoundSegmentSize = 7 );
  STATIC_CONST( MaxAccLockOps = MAX_PARALLEL_OP_PER_SCAN );
119 120 121 122 123 124
  BLOCK_DEFINES(Dbtux);

  // forward declarations
  struct DescEnt;

  /*
125
   * Pointer to array of Uint32.
126 127 128 129 130 131 132 133 134 135 136 137
   */
  struct Data {
  private:
    Uint32* m_data;
  public:
    Data();
    Data(Uint32* data);
    Data& operator=(Uint32* data);
    operator Uint32*() const;
    Data& operator+=(size_t n);
    AttributeHeader& ah() const;
  };
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
138
  friend class Data;
139 140

  /*
141
   * Pointer to array of constant Uint32.
142
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
143 144
  struct ConstData;
  friend struct ConstData;
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
  struct ConstData {
  private:
    const Uint32* m_data;
  public:
    ConstData();
    ConstData(const Uint32* data);
    ConstData& operator=(const Uint32* data);
    operator const Uint32*() const;
    ConstData& operator+=(size_t n);
    const AttributeHeader& ah() const;
    // non-const pointer can be cast to const pointer
    ConstData(Data data);
    ConstData& operator=(Data data);
  };

  // AttributeHeader size is assumed to be 1 word
161
  STATIC_CONST( AttributeHeaderSize = 1 );
162 163

  /*
164
   * Logical tuple address, "local key".  Identifies table tuples.
165 166
   */
  typedef Uint32 TupAddr;
167
  STATIC_CONST( NullTupAddr = (Uint32)-1 );
168 169 170 171 172

  /*
   * Physical tuple address in TUP.  Provides fast access to table tuple
   * or index node.  Valid within the db node and across timeslices.
   * Not valid between db nodes or across restarts.
173 174
   *
   * To avoid wasting an Uint16 the pageid is split in two.
175 176
   */
  struct TupLoc {
177 178 179
  private:
    Uint16 m_pageId1;           // page i-value (big-endian)
    Uint16 m_pageId2;
180
    Uint16 m_pageOffset;        // page offset in words
181
  public:
182
    TupLoc();
183
    TupLoc(Uint32 pageId, Uint16 pageOffset);
184 185 186 187
    Uint32 getPageId() const;
    void setPageId(Uint32 pageId);
    Uint32 getPageOffset() const;
    void setPageOffset(Uint32 pageOffset);
188 189
    bool operator==(const TupLoc& loc) const;
    bool operator!=(const TupLoc& loc) const;
190 191
  };

192
  /*
193
   * There is no const member NullTupLoc since the compiler may not be
194 195 196 197 198
   * able to optimize it to TupLoc() constants.  Instead null values are
   * constructed on the stack with TupLoc().
   */
#define NullTupLoc TupLoc()

199 200 201
  // tree definitions

  /*
202 203 204 205
   * Tree entry.  Points to a tuple in primary table via physical
   * address of "original" tuple and tuple version.
   *
   * ZTUP_VERSION_BITS must be 15 (or less).
206
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
207 208
  struct TreeEnt;
  friend struct TreeEnt;
209
  struct TreeEnt {
210 211 212
    TupLoc m_tupLoc;            // address of original tuple
    unsigned m_tupVersion : 15; // version
    unsigned m_fragBit : 1;     // which duplicated table fragment
213 214
    TreeEnt();
    // methods
215
    bool eq(const TreeEnt ent) const;
216 217
    int cmp(const TreeEnt ent) const;
  };
218
  STATIC_CONST( TreeEntSize = sizeof(TreeEnt) >> 2 );
219 220 221
  static const TreeEnt NullTreeEnt;

  /*
222 223
   * Tree node has 1) fixed part 2) a prefix of index key data for min
   * entry 3) max and min entries 4) rest of entries 5) one extra entry
224 225
   * used as work space.
   *
226
   * struct TreeNode            part 1, size 6 words
227 228 229 230 231 232
   * min prefix                 part 2, size TreeHead::m_prefSize
   * max entry                  part 3
   * min entry                  part 3
   * rest of entries            part 4
   * work entry                 part 5
   *
233
   * There are 3 links to other nodes: left child, right child, parent.
234
   * Occupancy (number of entries) is at least 1 except temporarily when
235
   * a node is about to be removed.
236
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
237 238
  struct TreeNode;
  friend struct TreeNode;
239
  struct TreeNode {
240
    TupLoc m_link[3];           // link to 0-left child 1-right child 2-parent
241
    unsigned m_side : 2;        // we are 0-left child 1-right child 2-root
242
    unsigned m_balance : 2;     // balance -1, 0, +1 plus 1 for Solaris CC
243
    unsigned pad1 : 4;
244 245 246 247
    Uint8 m_occup;              // current number of entries
    Uint32 m_nodeScan;          // list of scans at this node
    TreeNode();
  };
248
  STATIC_CONST( NodeHeadSize = sizeof(TreeNode) >> 2 );
249 250

  /*
251 252
   * Tree node "access size" was for an early version with signal
   * interface to TUP.  It is now used only to compute sizes.
253 254 255 256 257 258 259 260 261 262 263 264
   */
  enum AccSize {
    AccNone = 0,
    AccHead = 1,                // part 1
    AccPref = 2,                // parts 1-3
    AccFull = 3                 // parts 1-5
  };

  /*
   * Tree header.  There is one in each fragment.  Contains tree
   * parameters and address of root node.
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
265 266
  struct TreeHead;
  friend struct TreeHead;
267 268
  struct TreeHead {
    Uint8 m_nodeSize;           // words in tree node
269
    Uint8 m_prefSize;           // words in min prefix
270 271
    Uint8 m_minOccup;           // min entries in internal node
    Uint8 m_maxOccup;           // max entries in node
272
    TupLoc m_root;              // root node
273 274 275
    TreeHead();
    // methods
    unsigned getSize(AccSize acc) const;
276
    Data getPref(TreeNode* node) const;
277 278 279 280 281 282 283 284
    TreeEnt* getEntList(TreeNode* node) const;
  };

  /*
   * Tree position.  Specifies node, position within node (from 0 to
   * m_occup), and whether the position is at an existing entry or
   * before one (if any).  Position m_occup points past the node and is
   * also represented by position 0 of next node.  Includes direction
pekka@mysql.com's avatar
pekka@mysql.com committed
285
   * used by scan.
286
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
287 288
  struct TreePos;
  friend struct TreePos;
289
  struct TreePos {
290
    TupLoc m_loc;               // physical node address
291 292
    Uint16 m_pos;               // position 0 to m_occup
    Uint8 m_match;              // at an existing entry
pekka@mysql.com's avatar
pekka@mysql.com committed
293
    Uint8 m_dir;                // see scanNext()
294 295 296 297 298 299 300 301 302
    TreePos();
  };

  // packed metadata

  /*
   * Descriptor page.  The "hot" metadata for an index is stored as
   * a contiguous array of words on some page.
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
303 304
  struct DescPage;
  friend struct DescPage;
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
  struct DescPage {
    Uint32 m_nextPage;
    Uint32 m_numFree;           // number of free words
    union {
    Uint32 m_data[DescPageSize];
    Uint32 nextPool;
    };
    DescPage();
  };
  typedef Ptr<DescPage> DescPagePtr;
  ArrayPool<DescPage> c_descPagePool;
  Uint32 c_descPageList;

  /*
   * Header for index metadata.  Size must be multiple of word size.
   */
  struct DescHead {
    unsigned m_indexId : 24;
    unsigned pad1 : 8;
  };
325
  STATIC_CONST( DescHeadSize = sizeof(DescHead) >> 2 );
326 327 328

  /*
   * Attribute metadata.  Size must be multiple of word size.
329 330 331
   *
   * Prefix comparison of char data must use strxfrm and binary
   * comparison.  The charset is currently unused.
332 333
   */
  struct DescAttr {
334 335
    Uint32 m_attrDesc;          // standard AttributeDescriptor
    Uint16 m_primaryAttrId;
336 337
    unsigned m_typeId : 6;
    unsigned m_charset : 10;
338
  };
339
  STATIC_CONST( DescAttrSize = sizeof(DescAttr) >> 2 );
340 341 342 343 344

  /*
   * Complete metadata for one index. The array of attributes has
   * variable size.
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
345 346
  struct DescEnt;
  friend struct DescEnt;
347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
  struct DescEnt {
    DescHead m_descHead;
    DescAttr m_descAttr[1];     // variable size data
  };

  // range scan
 
  /*
   * Scan bounds are stored in linked list of segments.
   */
  typedef DataBuffer<ScanBoundSegmentSize> ScanBound;
  typedef DataBuffer<ScanBoundSegmentSize>::ConstDataBufferIterator ScanBoundIterator;
  typedef DataBuffer<ScanBoundSegmentSize>::DataBufferPool ScanBoundPool;
  ScanBoundPool c_scanBoundPool;
 
  /*
   * Scan operation.
   *
   * Tuples are locked one at a time.  The current lock op is set to
   * RNIL as soon as the lock is obtained and passed to LQH.  We must
   * however remember all locks which LQH has not returned for unlocking
   * since they must be aborted by us when the scan is closed.
   *
   * Scan state describes the entry we are interested in.  There is
   * a separate lock wait flag.  It may be for current entry or it may
   * be for an entry we were moved away from.  In any case nothing
   * happens with current entry before lock wait flag is cleared.
pekka@mysql.com's avatar
pekka@mysql.com committed
374 375 376 377
   *
   * An unfinished scan is always linked to some tree node, and has
   * current position and direction (see comments at scanNext).  There
   * is also a copy of latest entry found.
378
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
379 380
  struct ScanOp;
  friend struct ScanOp;
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
  struct ScanOp {
    enum {
      Undef = 0,
      First = 1,                // before first entry
      Current = 2,              // at current before locking
      Blocked = 3,              // at current waiting for ACC lock
      Locked = 4,               // at current and locked or no lock needed
      Next = 5,                 // looking for next extry
      Last = 6,                 // after last entry
      Aborting = 7,             // lock wait at scan close
      Invalid = 9               // cannot return REF to LQH currently
    };
    Uint16 m_state;
    Uint16 m_lockwait;
    Uint32 m_userPtr;           // scanptr.i in LQH
    Uint32 m_userRef;
    Uint32 m_tableId;
    Uint32 m_indexId;
    Uint32 m_fragId;
    Uint32 m_fragPtrI;
    Uint32 m_transId1;
    Uint32 m_transId2;
    Uint32 m_savePointId;
    // lock waited for or obtained and not yet passed to LQH
    Uint32 m_accLockOp;
    Uint8 m_readCommitted;      // no locking
    Uint8 m_lockMode;
408
    Uint8 m_descending;
409 410 411 412 413
    ScanBound m_boundMin;
    ScanBound m_boundMax;
    ScanBound* m_bound[2];      // pointers to above 2
    Uint16 m_boundCnt[2];       // number of bounds in each
    TreePos m_scanPos;          // position
pekka@mysql.com's avatar
pekka@mysql.com committed
414
    TreeEnt m_scanEnt;          // latest entry found
415 416 417 418 419 420
    Uint32 m_nodeScan;          // next scan at node (single-linked)
    union {
    Uint32 nextPool;
    Uint32 nextList;
    };
    Uint32 prevList;
421 422 423 424 425 426 427
    /*
     * Locks obtained and passed to LQH but not yet returned by LQH.
     * The max was increased from 16 to 992 (default 64).  Record max
     * ever used in this scan.  TODO fix quadratic behaviour
     */
    Uint32 m_maxAccLockOps;
    Uint32 m_accLockOps[MaxAccLockOps];
428 429 430 431 432 433 434 435 436 437 438
    ScanOp(ScanBoundPool& scanBoundPool);
  };
  typedef Ptr<ScanOp> ScanOpPtr;
  ArrayPool<ScanOp> c_scanOpPool;

  // indexes and fragments

  /*
   * Ordered index.  Top level data structure.  The primary table (table
   * being indexed) lives in TUP.
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
439 440
  struct Index;
  friend struct Index;
441 442 443 444 445 446 447 448 449 450
  struct Index {
    enum State {
      NotDefined = 0,
      Defining = 1,
      Online = 2,               // triggers activated and build done
      Dropping = 9
    };
    State m_state;
    DictTabInfo::TableType m_tableType;
    Uint32 m_tableId;
joreland@mysql.com's avatar
joreland@mysql.com committed
451
    Uint16 unused;
452 453 454 455 456 457
    Uint16 m_numFrags;
    Uint32 m_fragId[MaxIndexFragments];
    Uint32 m_fragPtrI[MaxIndexFragments];
    Uint32 m_descPage;          // descriptor page
    Uint16 m_descOff;           // offset within the page
    Uint16 m_numAttrs;
458
    bool m_storeNullKey;
459 460 461 462 463 464 465 466 467 468 469 470 471
    union {
    Uint32 nextPool;
    };
    Index();
  };
  typedef Ptr<Index> IndexPtr;
  ArrayPool<Index> c_indexPool;

  /*
   * Fragment of an index, as known to DIH/TC.  Represents the two
   * duplicate fragments known to LQH/ACC/TUP.  Includes tree header.
   * There are no maintenance operation records yet.
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
472 473
  struct Frag;
  friend struct Frag;
474 475 476
  struct Frag {
    Uint32 m_tableId;           // copy from index level
    Uint32 m_indexId;
joreland@mysql.com's avatar
joreland@mysql.com committed
477
    Uint16 unused;
478 479 480 481
    Uint16 m_fragId;
    Uint32 m_descPage;          // copy from index level
    Uint16 m_descOff;
    Uint16 m_numAttrs;
482
    bool m_storeNullKey;
483
    TreeHead m_tree;
484
    TupLoc m_freeLoc;           // list of free index nodes
485
    DLList<ScanOp> m_scanList;  // current scans on this fragment
486 487 488
    Uint32 m_tupIndexFragPtrI;
    Uint32 m_tupTableFragPtrI[2];
    Uint32 m_accTableFragPtrI[2];
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518
    union {
    Uint32 nextPool;
    };
    Frag(ArrayPool<ScanOp>& scanOpPool);
  };
  typedef Ptr<Frag> FragPtr;
  ArrayPool<Frag> c_fragPool;

  /*
   * Fragment metadata operation.
   */
  struct FragOp {
    Uint32 m_userPtr;
    Uint32 m_userRef;
    Uint32 m_indexId;
    Uint32 m_fragId;
    Uint32 m_fragPtrI;
    Uint32 m_fragNo;            // fragment number starting at zero
    Uint32 m_numAttrsRecvd;
    union {
    Uint32 nextPool;
    };
    FragOp();
  };
  typedef Ptr<FragOp> FragOpPtr;
  ArrayPool<FragOp> c_fragOpPool;

  // node handles

  /*
519 520
   * A node handle is a reference to a tree node in TUP.  It is used to
   * operate on the node.  Node handles are allocated on the stack.
521
   */
mysqldev@mysql.com's avatar
mysqldev@mysql.com committed
522 523
  struct NodeHandle;
  friend struct NodeHandle;
524 525 526
  struct NodeHandle {
    Frag& m_frag;               // fragment using the node
    TupLoc m_loc;               // physical node address
527 528
    TreeNode* m_node;           // pointer to node storage
    NodeHandle(Frag& frag);
529 530
    NodeHandle(const NodeHandle& node);
    NodeHandle& operator=(const NodeHandle& node);
531 532
    // check if unassigned
    bool isNull();
533
    // getters
534
    TupLoc getLink(unsigned i);
535 536 537 538 539 540
    unsigned getChilds();       // cannot spell
    unsigned getSide();
    unsigned getOccup();
    int getBalance();
    Uint32 getNodeScan();
    // setters
541
    void setLink(unsigned i, TupLoc loc);
542 543 544 545
    void setSide(unsigned i);
    void setOccup(unsigned n);
    void setBalance(int b);
    void setNodeScan(Uint32 scanPtrI);
546
    // access other parts of the node
547
    Data getPref();
548 549
    TreeEnt getEnt(unsigned pos);
    TreeEnt getMinMax(unsigned i);
550 551
    // for ndbrequire and ndbassert
    void progError(int line, int cause, const char* file);
552 553 554 555 556 557 558 559 560
  };

  // methods

  /*
   * DbtuxGen.cpp
   */
  void execCONTINUEB(Signal* signal);
  void execSTTOR(Signal* signal);
561
  void execREAD_CONFIG_REQ(Signal* signal);
562
  // utils
563
  void setKeyAttrs(const Frag& frag);
564 565 566
  void readKeyAttrs(const Frag& frag, TreeEnt ent, unsigned start, Data keyData);
  void readTablePk(const Frag& frag, TreeEnt ent, Data pkData, unsigned& pkSize);
  void copyAttrs(const Frag& frag, ConstData data1, Data data2, unsigned maxlen2 = MaxAttrDataSize);
567 568 569 570 571 572 573 574 575 576

  /*
   * DbtuxMeta.cpp
   */
  void execTUXFRAGREQ(Signal* signal);
  void execTUX_ADD_ATTRREQ(Signal* signal);
  void execALTER_INDX_REQ(Signal* signal);
  void execDROP_TAB_REQ(Signal* signal);
  bool allocDescEnt(IndexPtr indexPtr);
  void freeDescEnt(IndexPtr indexPtr);
577
  void abortAddFragOp(Signal* signal);
578 579 580 581 582 583 584 585 586 587
  void dropIndex(Signal* signal, IndexPtr indexPtr, Uint32 senderRef, Uint32 senderData);

  /*
   * DbtuxMaint.cpp
   */
  void execTUX_MAINT_REQ(Signal* signal);
  
  /*
   * DbtuxNode.cpp
   */
588
  int allocNode(Signal* signal, NodeHandle& node);
589 590 591 592
  void selectNode(NodeHandle& node, TupLoc loc);
  void insertNode(NodeHandle& node);
  void deleteNode(NodeHandle& node);
  void setNodePref(NodeHandle& node);
593
  // node operations
594 595 596 597 598 599 600 601 602
  void nodePushUp(NodeHandle& node, unsigned pos, const TreeEnt& ent, Uint32 scanList);
  void nodePushUpScans(NodeHandle& node, unsigned pos);
  void nodePopDown(NodeHandle& node, unsigned pos, TreeEnt& en, Uint32* scanList);
  void nodePopDownScans(NodeHandle& node, unsigned pos);
  void nodePushDown(NodeHandle& node, unsigned pos, TreeEnt& ent, Uint32& scanList);
  void nodePushDownScans(NodeHandle& node, unsigned pos);
  void nodePopUp(NodeHandle& node, unsigned pos, TreeEnt& ent, Uint32 scanList);
  void nodePopUpScans(NodeHandle& node, unsigned pos);
  void nodeSlide(NodeHandle& dstNode, NodeHandle& srcNode, unsigned cnt, unsigned i);
603
  // scans linked to node
604 605
  void addScanList(NodeHandle& node, unsigned pos, Uint32 scanList);
  void removeScanList(NodeHandle& node, unsigned pos, Uint32& scanList);
606
  void moveScanList(NodeHandle& node, unsigned pos);
607 608 609
  void linkScan(NodeHandle& node, ScanOpPtr scanPtr);
  void unlinkScan(NodeHandle& node, ScanOpPtr scanPtr);
  bool islinkScan(NodeHandle& node, ScanOpPtr scanPtr);
610 611 612 613

  /*
   * DbtuxTree.cpp
   */
614
  // add entry
615 616 617 618
  void treeAdd(Frag& frag, TreePos treePos, TreeEnt ent);
  void treeAddFull(Frag& frag, NodeHandle lubNode, unsigned pos, TreeEnt ent);
  void treeAddNode(Frag& frag, NodeHandle lubNode, unsigned pos, TreeEnt ent, NodeHandle parentNode, unsigned i);
  void treeAddRebalance(Frag& frag, NodeHandle node, unsigned i);
619
  // remove entry
620 621 622 623 624 625
  void treeRemove(Frag& frag, TreePos treePos);
  void treeRemoveInner(Frag& frag, NodeHandle lubNode, unsigned pos);
  void treeRemoveSemi(Frag& frag, NodeHandle node, unsigned i);
  void treeRemoveLeaf(Frag& frag, NodeHandle node);
  void treeRemoveNode(Frag& frag, NodeHandle node);
  void treeRemoveRebalance(Frag& frag, NodeHandle node, unsigned i);
626
  // rotate
627 628
  void treeRotateSingle(Frag& frag, NodeHandle& node, unsigned i);
  void treeRotateDouble(Frag& frag, NodeHandle& node, unsigned i);
629 630 631 632 633 634 635 636 637 638 639

  /*
   * DbtuxScan.cpp
   */
  void execACC_SCANREQ(Signal* signal);
  void execTUX_BOUND_INFO(Signal* signal);
  void execNEXT_SCANREQ(Signal* signal);
  void execACC_CHECK_SCAN(Signal* signal);
  void execACCKEYCONF(Signal* signal);
  void execACCKEYREF(Signal* signal);
  void execACC_ABORTCONF(Signal* signal);
640
  void scanFirst(ScanOpPtr scanPtr);
641
  void scanNext(ScanOpPtr scanPtr, bool fromMaintReq);
642
  bool scanVisible(ScanOpPtr scanPtr, TreeEnt ent);
643 644 645 646 647
  void scanClose(Signal* signal, ScanOpPtr scanPtr);
  void addAccLockOp(ScanOp& scan, Uint32 accLockOp);
  void removeAccLockOp(ScanOp& scan, Uint32 accLockOp);
  void releaseScanOp(ScanOpPtr& scanPtr);

648 649 650
  /*
   * DbtuxSearch.cpp
   */
651 652
  void searchToAdd(Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos);
  void searchToRemove(Frag& frag, ConstData searchKey, TreeEnt searchEnt, TreePos& treePos);
653 654 655
  void searchToScan(Frag& frag, ConstData boundInfo, unsigned boundCount, bool descending, TreePos& treePos);
  void searchToScanAscending(Frag& frag, ConstData boundInfo, unsigned boundCount, TreePos& treePos);
  void searchToScanDescending(Frag& frag, ConstData boundInfo, unsigned boundCount, TreePos& treePos);
656

657 658 659
  /*
   * DbtuxCmp.cpp
   */
660
  int cmpSearchKey(const Frag& frag, unsigned& start, ConstData searchKey, ConstData entryData, unsigned maxlen = MaxAttrDataSize);
661
  int cmpScanBound(const Frag& frag, unsigned dir, ConstData boundInfo, unsigned boundCount, ConstData entryData, unsigned maxlen = MaxAttrDataSize);
662 663 664 665 666 667 668 669 670

  /*
   * DbtuxDebug.cpp
   */
  void execDUMP_STATE_ORD(Signal* signal);
#ifdef VM_TRACE
  struct PrintPar {
    char m_path[100];           // LR prefix
    unsigned m_side;            // expected side
671
    TupLoc m_parent;            // expected parent address
672 673
    int m_depth;                // returned depth
    unsigned m_occup;           // returned occupancy
674
    TreeEnt m_minmax[2];        // returned subtree min and max
675 676 677 678
    bool m_ok;                  // returned status
    PrintPar();
  };
  void printTree(Signal* signal, Frag& frag, NdbOut& out);
679
  void printNode(Frag& frag, NdbOut& out, TupLoc loc, PrintPar& par);
680
  friend class NdbOut& operator<<(NdbOut&, const TupLoc&);
681 682 683 684 685
  friend class NdbOut& operator<<(NdbOut&, const TreeEnt&);
  friend class NdbOut& operator<<(NdbOut&, const TreeNode&);
  friend class NdbOut& operator<<(NdbOut&, const TreeHead&);
  friend class NdbOut& operator<<(NdbOut&, const TreePos&);
  friend class NdbOut& operator<<(NdbOut&, const DescAttr&);
686
  friend class NdbOut& operator<<(NdbOut&, const ScanOp&);
687 688
  friend class NdbOut& operator<<(NdbOut&, const Index&);
  friend class NdbOut& operator<<(NdbOut&, const Frag&);
689
  friend class NdbOut& operator<<(NdbOut&, const FragOp&);
690 691 692 693 694 695 696 697 698 699
  friend class NdbOut& operator<<(NdbOut&, const NodeHandle&);
  FILE* debugFile;
  NdbOut debugOut;
  unsigned debugFlags;
  enum {
    DebugMeta = 1,              // log create and drop index
    DebugMaint = 2,             // log maintenance ops
    DebugTree = 4,              // log and check tree after each op
    DebugScan = 8               // log scans
  };
700 701
  STATIC_CONST( DataFillByte = 0xa2 );
  STATIC_CONST( NodeFillByte = 0xa4 );
702 703 704 705 706 707
#endif

  // start up info
  Uint32 c_internalStartPhase;
  Uint32 c_typeOfStart;

708
  /*
709 710 711 712
   * Global data set at operation start.  Unpacked from index metadata.
   * Not passed as parameter to methods.  Invalid across timeslices.
   *
   * TODO inline all into index metadata
713
   */
714 715

  // index key attr ids with sizes in AttributeHeader format
716 717
  Data c_keyAttrs;

718 719 720 721 722 723 724 725 726
  // pointers to index key comparison functions
  NdbSqlUtil::Cmp** c_sqlCmp;

  /*
   * Other buffers used during the operation.
   */

  // buffer for search key data with headers
  Data c_searchKey;
727

728 729
  // buffer for current entry key data with headers
  Data c_entryKey;
730

731 732 733
  // buffer for scan bounds and keyinfo (primary key)
  Data c_dataBuffer;

734 735
  // inlined utils
  DescEnt& getDescEnt(Uint32 descPage, Uint32 descOff);
736
  Uint32 getTupAddr(const Frag& frag, TreeEnt ent);
737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833
  static unsigned min(unsigned x, unsigned y);
  static unsigned max(unsigned x, unsigned y);
};

// Dbtux::Data

inline
Dbtux::Data::Data() :
  m_data(0)
{
}

inline
Dbtux::Data::Data(Uint32* data) :
  m_data(data)
{
}

inline Dbtux::Data&
Dbtux::Data::operator=(Uint32* data)
{
  m_data = data;
  return *this;
}

inline
Dbtux::Data::operator Uint32*() const
{
  return m_data;
}

inline Dbtux::Data&
Dbtux::Data::operator+=(size_t n)
{
  m_data += n;
  return *this;
}

inline AttributeHeader&
Dbtux::Data::ah() const
{
  return *reinterpret_cast<AttributeHeader*>(m_data);
}

// Dbtux::ConstData

inline
Dbtux::ConstData::ConstData() :
  m_data(0)
{
}

inline
Dbtux::ConstData::ConstData(const Uint32* data) :
  m_data(data)
{
}

inline Dbtux::ConstData&
Dbtux::ConstData::operator=(const Uint32* data)
{
  m_data = data;
  return *this;
}

inline
Dbtux::ConstData::operator const Uint32*() const
{
  return m_data;
}

inline Dbtux::ConstData&
Dbtux::ConstData::operator+=(size_t n)
{
  m_data += n;
  return *this;
}

inline const AttributeHeader&
Dbtux::ConstData::ah() const
{
  return *reinterpret_cast<const AttributeHeader*>(m_data);
}

inline
Dbtux::ConstData::ConstData(Data data) :
  m_data(static_cast<Uint32*>(data))
{
}

inline Dbtux::ConstData&
Dbtux::ConstData::operator=(Data data)
{
  m_data = static_cast<Uint32*>(data);
  return *this;
}

834 835 836 837
// Dbtux::TupLoc

inline
Dbtux::TupLoc::TupLoc() :
838 839
  m_pageId1(RNIL >> 16),
  m_pageId2(RNIL & 0xFFFF),
840 841 842 843 844 845
  m_pageOffset(0)
{
}

inline
Dbtux::TupLoc::TupLoc(Uint32 pageId, Uint16 pageOffset) :
846 847
  m_pageId1(pageId >> 16),
  m_pageId2(pageId & 0xFFFF),
848 849 850 851
  m_pageOffset(pageOffset)
{
}

852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876
inline Uint32
Dbtux::TupLoc::getPageId() const
{
  return (m_pageId1 << 16) | m_pageId2;
}

inline void
Dbtux::TupLoc::setPageId(Uint32 pageId)
{
  m_pageId1 = (pageId >> 16);
  m_pageId2 = (pageId & 0xFFFF);
}

inline Uint32
Dbtux::TupLoc::getPageOffset() const
{
  return (Uint32)m_pageOffset;
}

inline void
Dbtux::TupLoc::setPageOffset(Uint32 pageOffset)
{
  m_pageOffset = (Uint16)pageOffset;
}

877 878 879
inline bool
Dbtux::TupLoc::operator==(const TupLoc& loc) const
{
880 881 882 883
  return
    m_pageId1 == loc.m_pageId1 &&
    m_pageId2 == loc.m_pageId2 &&
    m_pageOffset == loc.m_pageOffset;
884 885 886 887 888 889 890 891
}

inline bool
Dbtux::TupLoc::operator!=(const TupLoc& loc) const
{
  return ! (*this == loc);
}

892 893
// Dbtux::TreeEnt

894 895
inline
Dbtux::TreeEnt::TreeEnt() :
896
  m_tupLoc(),
897
  m_tupVersion(0),
898
  m_fragBit(0)
899 900 901
{
}

902 903 904 905 906 907 908 909 910
inline bool
Dbtux::TreeEnt::eq(const TreeEnt ent) const
{
  return
    m_tupLoc == ent.m_tupLoc &&
    m_tupVersion == ent.m_tupVersion &&
    m_fragBit == ent.m_fragBit;
}

911 912 913
inline int
Dbtux::TreeEnt::cmp(const TreeEnt ent) const
{
914
  if (m_tupLoc.getPageId() < ent.m_tupLoc.getPageId())
915
    return -1;
916
  if (m_tupLoc.getPageId() > ent.m_tupLoc.getPageId())
917
    return +1;
918
  if (m_tupLoc.getPageOffset() < ent.m_tupLoc.getPageOffset())
919
    return -1;
920
  if (m_tupLoc.getPageOffset() > ent.m_tupLoc.getPageOffset())
921 922 923 924 925
    return +1;
  if (m_tupVersion < ent.m_tupVersion)
    return -1;
  if (m_tupVersion > ent.m_tupVersion)
    return +1;
926 927 928 929
  if (m_fragBit < ent.m_fragBit)
    return -1;
  if (m_fragBit > ent.m_fragBit)
    return +1;
930 931 932
  return 0;
}

933 934 935 936 937
// Dbtux::TreeNode

inline
Dbtux::TreeNode::TreeNode() :
  m_side(2),
938
  m_balance(0 + 1),
939 940 941 942
  pad1(0),
  m_occup(0),
  m_nodeScan(RNIL)
{
943 944 945
  m_link[0] = NullTupLoc;
  m_link[1] = NullTupLoc;
  m_link[2] = NullTupLoc;
946 947
}

948 949
// Dbtux::TreeHead

950 951 952 953 954 955 956 957 958 959
inline
Dbtux::TreeHead::TreeHead() :
  m_nodeSize(0),
  m_prefSize(0),
  m_minOccup(0),
  m_maxOccup(0),
  m_root()
{
}

960 961 962 963 964 965 966 967 968
inline unsigned
Dbtux::TreeHead::getSize(AccSize acc) const
{
  switch (acc) {
  case AccNone:
    return 0;
  case AccHead:
    return NodeHeadSize;
  case AccPref:
969
    return NodeHeadSize + m_prefSize + 2 * TreeEntSize;
970 971 972 973 974 975 976
  case AccFull:
    return m_nodeSize;
  }
  return 0;
}

inline Dbtux::Data
977
Dbtux::TreeHead::getPref(TreeNode* node) const
978
{
979
  Uint32* ptr = (Uint32*)node + NodeHeadSize;
980 981 982 983 984 985
  return ptr;
}

inline Dbtux::TreeEnt*
Dbtux::TreeHead::getEntList(TreeNode* node) const
{
986
  Uint32* ptr = (Uint32*)node + NodeHeadSize + m_prefSize;
987 988 989
  return (TreeEnt*)ptr;
}

990
// Dbtux::TreePos
991 992 993 994 995 996

inline
Dbtux::TreePos::TreePos() :
  m_loc(),
  m_pos(ZNIL),
  m_match(false),
pekka@mysql.com's avatar
pekka@mysql.com committed
997
  m_dir(255)
998 999 1000
{
}

1001 1002
// Dbtux::DescPage

1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016
inline
Dbtux::DescPage::DescPage() :
  m_nextPage(RNIL),
  m_numFree(ZNIL)
{
  for (unsigned i = 0; i < DescPageSize; i++) {
#ifdef VM_TRACE
    m_data[i] = 0x13571357;
#else
    m_data[i] = 0;
#endif
  }
}

1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033
// Dbtux::ScanOp

inline
Dbtux::ScanOp::ScanOp(ScanBoundPool& scanBoundPool) :
  m_state(Undef),
  m_lockwait(false),
  m_userPtr(RNIL),
  m_userRef(RNIL),
  m_tableId(RNIL),
  m_indexId(RNIL),
  m_fragPtrI(RNIL),
  m_transId1(0),
  m_transId2(0),
  m_savePointId(0),
  m_accLockOp(RNIL),
  m_readCommitted(0),
  m_lockMode(0),
1034
  m_descending(0),
1035 1036 1037
  m_boundMin(scanBoundPool),
  m_boundMax(scanBoundPool),
  m_scanPos(),
pekka@mysql.com's avatar
pekka@mysql.com committed
1038
  m_scanEnt(),
1039 1040
  m_nodeScan(RNIL),
  m_maxAccLockOps(0)
1041 1042 1043 1044 1045
{
  m_bound[0] = &m_boundMin;
  m_bound[1] = &m_boundMax;
  m_boundCnt[0] = 0;
  m_boundCnt[1] = 0;
1046
#ifdef VM_TRACE
1047
  for (unsigned i = 0; i < MaxAccLockOps; i++) {
1048
    m_accLockOps[i] = 0x1f1f1f1f;
1049
  }
1050
#endif
1051 1052 1053 1054
}

// Dbtux::Index

1055 1056 1057 1058 1059 1060 1061 1062
inline
Dbtux::Index::Index() :
  m_state(NotDefined),
  m_tableType(DictTabInfo::UndefTableType),
  m_tableId(RNIL),
  m_numFrags(0),
  m_descPage(RNIL),
  m_descOff(0),
1063 1064
  m_numAttrs(0),
  m_storeNullKey(false)
1065 1066 1067 1068 1069
{
  for (unsigned i = 0; i < MaxIndexFragments; i++) {
    m_fragId[i] = ZNIL;
    m_fragPtrI[i] = RNIL;
  };
1070
}
1071

1072 1073
// Dbtux::Frag

1074 1075 1076 1077 1078 1079 1080 1081
inline
Dbtux::Frag::Frag(ArrayPool<ScanOp>& scanOpPool) :
  m_tableId(RNIL),
  m_indexId(RNIL),
  m_fragId(ZNIL),
  m_descPage(RNIL),
  m_descOff(0),
  m_numAttrs(ZNIL),
1082
  m_storeNullKey(false),
1083
  m_tree(),
1084
  m_freeLoc(),
1085 1086
  m_scanList(scanOpPool),
  m_tupIndexFragPtrI(RNIL)
1087
{
1088 1089 1090 1091
  m_tupTableFragPtrI[0] = RNIL;
  m_tupTableFragPtrI[1] = RNIL;
  m_accTableFragPtrI[0] = RNIL;
  m_accTableFragPtrI[1] = RNIL;
1092 1093
}

1094 1095
// Dbtux::FragOp

1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
inline
Dbtux::FragOp::FragOp() :
  m_userPtr(RNIL),
  m_userRef(RNIL),
  m_indexId(RNIL),
  m_fragId(ZNIL),
  m_fragPtrI(RNIL),
  m_fragNo(ZNIL),
  m_numAttrsRecvd(ZNIL)
{
1106
}
1107

1108 1109
// Dbtux::NodeHandle

1110
inline
1111
Dbtux::NodeHandle::NodeHandle(Frag& frag) :
1112 1113
  m_frag(frag),
  m_loc(),
1114
  m_node(0)
1115 1116 1117
{
}

1118 1119 1120 1121
inline
Dbtux::NodeHandle::NodeHandle(const NodeHandle& node) :
  m_frag(node.m_frag),
  m_loc(node.m_loc),
1122
  m_node(node.m_node)
1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134
{
}

inline Dbtux::NodeHandle&
Dbtux::NodeHandle::operator=(const NodeHandle& node)
{
  ndbassert(&m_frag == &node.m_frag);
  m_loc = node.m_loc;
  m_node = node.m_node;
  return *this;
}

1135 1136 1137 1138 1139 1140
inline bool
Dbtux::NodeHandle::isNull()
{
  return m_node == 0;
}

1141
inline Dbtux::TupLoc
1142 1143 1144
Dbtux::NodeHandle::getLink(unsigned i)
{
  ndbrequire(i <= 2);
1145
  return m_node->m_link[i];
1146 1147 1148 1149 1150
}

inline unsigned
Dbtux::NodeHandle::getChilds()
{
1151
  return (m_node->m_link[0] != NullTupLoc) + (m_node->m_link[1] != NullTupLoc);
1152 1153
}

1154
inline unsigned
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168
Dbtux::NodeHandle::getSide()
{
  return m_node->m_side;
}

inline unsigned
Dbtux::NodeHandle::getOccup()
{
  return m_node->m_occup;
}

inline int
Dbtux::NodeHandle::getBalance()
{
1169
  return (int)m_node->m_balance - 1;
1170 1171 1172 1173 1174 1175 1176 1177 1178
}

inline Uint32
Dbtux::NodeHandle::getNodeScan()
{
  return m_node->m_nodeScan;
}

inline void
1179
Dbtux::NodeHandle::setLink(unsigned i, TupLoc loc)
1180 1181
{
  ndbrequire(i <= 2);
1182
  m_node->m_link[i] = loc;
1183 1184 1185 1186 1187
}

inline void
Dbtux::NodeHandle::setSide(unsigned i)
{
1188
  ndbrequire(i <= 2);
1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203
  m_node->m_side = i;
}

inline void
Dbtux::NodeHandle::setOccup(unsigned n)
{
  TreeHead& tree = m_frag.m_tree;
  ndbrequire(n <= tree.m_maxOccup);
  m_node->m_occup = n;
}

inline void
Dbtux::NodeHandle::setBalance(int b)
{
  ndbrequire(abs(b) <= 1);
1204
  m_node->m_balance = (unsigned)(b + 1);
1205 1206 1207 1208 1209 1210 1211 1212
}

inline void
Dbtux::NodeHandle::setNodeScan(Uint32 scanPtrI)
{
  m_node->m_nodeScan = scanPtrI;
}

1213
inline Dbtux::Data
1214
Dbtux::NodeHandle::getPref()
1215 1216
{
  TreeHead& tree = m_frag.m_tree;
1217
  return tree.getPref(m_node);
1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237
}

inline Dbtux::TreeEnt
Dbtux::NodeHandle::getEnt(unsigned pos)
{
  TreeHead& tree = m_frag.m_tree;
  TreeEnt* entList = tree.getEntList(m_node);
  const unsigned occup = m_node->m_occup;
  ndbrequire(pos < occup);
  return entList[(1 + pos) % occup];
}

inline Dbtux::TreeEnt
Dbtux::NodeHandle::getMinMax(unsigned i)
{
  const unsigned occup = m_node->m_occup;
  ndbrequire(i <= 1 && occup != 0);
  return getEnt(i == 0 ? 0 : occup - 1);
}

1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254
// parameters for methods

#ifdef VM_TRACE
inline
Dbtux::PrintPar::PrintPar() :
  // caller fills in
  m_path(),
  m_side(255),
  m_parent(),
  // default return values
  m_depth(0),
  m_occup(0),
  m_ok(true)
{
}
#endif

1255
// utils
1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267

inline Dbtux::DescEnt&
Dbtux::getDescEnt(Uint32 descPage, Uint32 descOff)
{
  DescPagePtr pagePtr;
  pagePtr.i = descPage;
  c_descPagePool.getPtr(pagePtr);
  ndbrequire(descOff < DescPageSize);
  DescEnt* descEnt = (DescEnt*)&pagePtr.p->m_data[descOff];
  return *descEnt;
}

1268
inline Uint32
1269
Dbtux::getTupAddr(const Frag& frag, TreeEnt ent)
1270 1271 1272 1273
{
  const Uint32 tableFragPtrI = frag.m_tupTableFragPtrI[ent.m_fragBit];
  const TupLoc tupLoc = ent.m_tupLoc;
  Uint32 tupAddr = NullTupAddr;
1274
  c_tup->tuxGetTupAddr(tableFragPtrI, tupLoc.getPageId(), tupLoc.getPageOffset(), tupAddr);
1275
  jamEntry();
1276 1277 1278
  return tupAddr;
}

1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291
inline unsigned
Dbtux::min(unsigned x, unsigned y)
{
  return x < y ? x : y;
}

inline unsigned
Dbtux::max(unsigned x, unsigned y)
{
  return x > y ? x : y;
}

#endif