Agenda

0. The problem — what a lock manager is for
1. Theory — 2PL phases & variants, MGL, lub; what every DBMS lock manager shares
2. Data structures — OID keys, LK_ENTRY dual-view, lk_Gl, boot & memory tiers
3. The life of a lock request — paths A–G, conversion & UPR, release & NON2PL, escalation, suspend/resume
4. Deadlock — WFG construction, cycle scan, six-criteria victim selection
5. Special paths — instant probe, composite lock, hint / demote / subclass

Sources: cubrid-lock-manager.md (design intent) + cubrid-lock-manager-detail.md (code-level deep dive).
Appendix A: Lock vs Latch, in depth. Appendix B: the lock-table hash function.

Start conservative — one transaction at a time

The trivially correct scheduler: one exclusive lock on the entire database.

• Serial by construction — every transaction has the database to itself, so nothing can possibly go wrong. The cost: a 10 ms read stuck behind a 10 s batch waits 1,000× longer than its own work.
• The fix is a dial, not a switch: shrink the unit of exclusion — database → class → row — so non-overlapping work runs in parallel. The same dial returns at intention modes and escalation.
• Shrinking the grain is what admits interleavings — the next slide catalogs the five you just let in.

The problem — what a lock manager is for

Interleave transactions on shared data without coordination and ACID's I (Isolation) breaks — exactly five classical anomalies appear:

• Goal: keep the concurrency but stay serializable — every result one a serial run (previous slide) could have produced.
• Lock manager's role: the lock primitive — "I am reading / writing this object" — plus conflict arbitration (grant, queue, escalate, abort as deadlock victim).
• Locks alone are not enough: lock-and-release per access still fails — the moment T₁ releases R, T₂ slips in between its steps; the missing piece is a discipline on lock timing → next slide.
• Isolation levels (RC / RR / Serializable) are tunable trade-offs: which anomalies you tolerate for more concurrency.

2PL — two phases, one lock point

How to allow interleavings and still be equivalent to some serial run? The classical answer:

• Growing phase: a transaction may acquire any lock; once one is released, the shrinking phase has begun.
• Shrinking phase: only releases are allowed. No further acquires.
• The transition is the lock point — it does not have to be at commit time, but everything ordered around it determines the schedule.
• Theorem (Eswaran 1976): if every transaction observes 2PL, the resulting schedule is serializable.

Two-phase locking is a discipline on the timing of lock(R) / unlock(R) calls, not on which locks are held.

2PL variants — basic, strict, rigorous

• What rigorous buys on top: holding every lock — S included — to commit makes the serialization order equal the commit order, so replicas and log readers can trust the order they observe. The price: read locks block writers until commit.
• Cascading abort: if T₁ releases an X lock on R before committing and T₂ reads R, then T₁ aborts, T₂ must abort too. Strict 2PL forbids this by construction.
• CUBRID uses strict 2PL for X locks — every X lock holds to commit. Reads are MVCC: plain SELECT on user tables takes no row lock. The RC-vs-RR S-lock release knob applies only to MVCC-disabled classes (root, serials, collation, HA apply-info) via lock_unlock_object_by_isolation.

"Strict" is the line WAL recovery assumes — undo at abort works only because no other transaction has seen our writes yet.

Worked example — one abort drags down everyone downstream

T1 follows basic 2PL to the letter — and still poisons two other transactions:

• This is the dirty read from §The problem, weaponized: the write became visible before commit, so one rollback cascades through every downstream reader, recursively.
• The cure is blunt: hold X locks to commit (strict 2PL). Nobody can read your writes early — the chain can never start. CUBRID applies this to X locks unconditionally.

Cost of 2PL — and the four standard remedies

• Guarantee: serializable schedules (no anomaly).
• Cost #1: contention. Long shrinking phases serialize the workload.
• Cost #2: deadlocks. Hold-and-wait + circular dependency is unavoidable in general.
• Four standard remedies:
  • Timeout — cheap to implement, prone to false positives under load.
  • Conservative 2PL — acquire every lock up front, before doing any work. Avoids deadlock entirely, but caller must know its working set.
  • Waits-for graph cycle scan ← CUBRID's primary detector (lock_detect_local_deadlock).
  • Timestamp avoidance — wait-die, wound-wait. Decides who waits using transaction age; common in distributed designs (Spanner, CockroachDB), rare in monolithic DBMSs.

CUBRID picks WFG detection as the primary mechanism and falls back to per-request timeout when WFG maintenance lags.

Three theoretical building blocks

Beyond plain S/X locks, three pieces of theory shape every real lock manager:

1. Intention modes (IS, IX, SIX) — multi-granularity locking. A coarse lock declares intent to take finer locks underneath, so two transactions can lock different rows of the same table without false table-level conflict.
2. Compatibility matrix — 2×2 (S, X) → 5×5 (with intention) → 12×12 in CUBRID (add BU, SCH-S/M, U, NON2PL).
3. Conversion — re-requesting your own lock should upgrade, not deadlock with yourself. The new mode is the least upper bound (lub) of held and requested.
   Definition. In the lock-mode lattice, lub(A, B) is the smallest mode that satisfies both A and B. E.g. lub(S, IX) = SIX, lub(IS, S) = S, lub(S, X) = X.

The data structures in Part II realize these three pieces as LK_ENTRY + the lock-mode matrix + a conversion table.

Why intention modes exist

Without intention modes (IS, IX, SIX) you face a binary choice for class-grain locking:

Intention modes solve both at once. Taking IX on a class declares "I will hold an X on at least one row underneath." Then:

• Two writers on different rows can both hold IX on the class — no conflict (IX ∧ IX = ✓).
• DDL takes SCH-M, which conflicts with IX — writers wait for the DDL to commit, but fine-grained concurrency between writers is preserved.
• A reader who needs S on the whole class still conflicts with IX — correct, because someone's writing a row.

Without IS/IX/SIX, MGL collapses back to S/X-only. With them, you get row-grain data concurrency + class-grain DDL protection in the same compatibility matrix.

Seven common DBMS patterns

1. Lock vs latch separation — lock = logical, transaction-long, in the external lock table (LK_ENTRY); latch = physical, microseconds, inside the page (PGBUF_LATCH). Depth: Appendix A
2. Resource hashing — OID, or (relation, key range)
3. Aggregate-mode cache — total_holders_mode (O(holders) → O(1))
4. Dual-view threading — resource view + transaction view
5. MGL + intention modes — IS, IX, S, SIX, X
6. Conversion (lub) table — S + IX = SIX
7. FIFO queue + starvation guard — holders ∧ waiters

None of these seven is a CUBRID invention — every serious engine sets the same seven dials. Part II shows the position CUBRID chose for each one.

Overview — how a lock request flows

• Two grains, one exception. Intent at the class first; the row lock is real for writes and MVCC-disabled reads — plain reads on MVCC tables skip it (snapshot visibility).
• Compatibility is two-sided — granted modes and the wait queue (the starvation guard). A suspend ends one of three ways: granted by a releaser, timeout, or deadlock-victim rollback.
• Release timing is scoped. Per-statement release exists only for S locks on MVCC-disabled classes under RC; everything else — X, class, intent — holds to commit.

Naming everything with OID

• OID = (volid, pageid, slotid) — the db_identifier C struct; the tuples above are examples.
• Granularity hierarchy = OID hierarchy: Root class → Class → Instance.
• Every parent→child arrow above is exactly an intention-lock parent/child edge — the hierarchies mirror one-for-one.

Three core types

// src/transaction/lock_manager.h
struct lk_res_key { LOCK_RESOURCE_TYPE type; OID oid; OID class_oid; };

struct lk_res {
  LK_RES_KEY key;
  LOCK       total_holders_mode;   // aggregate of granted modes
  LOCK       total_waiters_mode;   // aggregate of waiting modes
  LK_ENTRY  *holder, *waiter, *non2pl;
  pthread_mutex_t res_mutex;
};

struct lk_entry {
  LK_RES   *res_head;
  int       tran_index;
  LOCK      granted_mode, blocked_mode;
  int       count;                 // re-entrant counter
  LK_ENTRY *next;                  // resource list (holder or waiter)
  LK_ENTRY *tran_next, *tran_prev; // transaction list
  LK_ENTRY *class_entry;           // parent class, one hop
  int       ngranules;             // children below this intention lock
};

Watch three field pairs: the two aggregate modes (O(1) compatibility — §matrix), the two mode fields on LK_ENTRY (conversion state — §paths F/G), and the two linkages next vs tran_next/prev (§dual-view).

LK_TRAN_LOCK — one transaction's lock state

// struct lk_tran_lock — src/transaction/lock_manager.c
struct lk_tran_lock {
  LK_ENTRY *inst_hold_list, *class_hold_list, *root_class_hold;
  LK_ENTRY *waiting;             // the one lock this txn is blocked on
  LK_ENTRY *lk_entry_pool;       // local LK_ENTRY pool, max 10
  LK_ENTRY *non2pl_list;         // early-released lock shadows (RC)
  bool      lock_escalation_on;  // escalation re-entrance guard
  bool      is_instant_duration; // instant-lock mode flag
};

• Three hold lists, split by grain — "what do I hold on class A?" walks only class_hold_list: O(classes held), not O(all locks).
• waiting is singular — a transaction blocks on at most one lock at a time.
• The 10-entry local pool, the escalation guard, and the instant flag each return in the memory / escalation / special-path slides.

The global lock table — lk_global_data

Three globals: the hash table, the per-tran table with a 10-entry local pool, a shared freelist for overflow. Sizing: §Boot.

lk_Gl in action — one contended row, two views

Scenario: T7 is mid-UPDATE on a row of class A; T9's UPDATE of the same row has to wait.

Resource view — m_obj_hash_table:

Transaction view — tran_lock_table:

• The two bold cells are one and the same LK_ENTRY — threaded into the resource's holder list and T7's hold list at once (§Dual-view, two slides ahead).
• Both transactions hold IX on the class with zero conflict — the real fight happens one grain below.

Entry initialization — granted vs blocked

// lock_initialize_entry_as_granted — src/transaction/lock_manager.c
  e->tran_index   = tran;          e->res_head = res;
  e->granted_mode = lock;          // → this entry is a holder
  e->blocked_mode = NULL_LOCK;
  e->count        = 1;             /* list pointers nulled */

// lock_initialize_entry_as_blocked — same file
  e->thrd_entry   = th;            // the thread to suspend
  e->granted_mode = NULL_LOCK;
  e->blocked_mode = lock;          // → this entry is a waiter

• One entry per (resource, txn) — the field pair plus which list it threads is the state. (blocked_mode is a pending target, not an "intention" — that word belongs to IS/IX/SIX.) A third constructor builds the §NON2PL shadows — not a lock at all.

Dual-View Threading

• The same LK_ENTRY lives in two lists at once.
• Resource view: who holds R? → next.   Txn view: what does T hold? → tran_next/prev.
• Commit walks the txn list. Compatibility check reads the resource-side aggregate.

Boot — lock_initialize, five steps in order

• Steps 1–4 populate the lk_Gl globals from the assembly diagram (colors match); step 5 starts the only background thread. Functions: lock_initialize_* — full walk in detail ch. 2.
• Order is load-bearing — step 4 sizes the WFG by num_trans, which step 1 sets.
• The daemon does three duties per 100 ms tick: interrupt check, timeout check, and the (gated) deadlock scan — 100 ms is the timeout granularity, by design.

Memory — three tiers, and the lockfree boundary

• A 3–5-row OLTP transaction never leaves tier 1 — allocation is contention-free.
• The boundary: finding an LK_RES (hash find_or_insert) is lockfree; mutating its lists is mutex-guarded — res_mutex per resource, hold_mutex per transaction.
• Retired entries reclaim epoch-based (del_id) — the same machinery as CUBRID's other lockfree modules.

A 12-mode vocabulary

Gray's 5 modes (IS / IX / S / SIX / X) + CUBRID's 7 extras.

How SQL statements map to lock modes

A statement typically takes two locks: an intent at class grain — planted by lock_object's MGL preparation, or by lock_scan at heap-scan start — and a real lock at row grain.

• The IX row repeats deliberately — every row-level write takes the same class-level intent mode. The compatibility matrix does the rest.

Compatibility matrix + starvation guard

A new request must be compatible with both total_holders_mode and total_waiters_mode — the latter is the starvation guard that stops a stream of S from leapfrogging a waiting X.

Worked example — the starvation guard at work

A shape you can reproduce on any CUBRID table — long reader, then DDL, then more readers (class grain):

• At t = 3 a holders-only test would grant T3 (IS ∧ IS = ✓) — and a steady stream of readers would starve the DDL forever. The waiter check queues T3 behind T2; the ALTER runs as soon as T1 finishes.
• A row-grain version of this story exists only on MVCC-disabled rows (serials) — plain MVCC readers never take row S locks.

PostgreSQL ships the same rule as strong-lock fairness; in CUBRID it is the total_waiters_mode side of the dual test.

Who calls the lock manager

The lock manager is a service layer: ten files account for ~90 % of all call sites.

Two entry points, one internal workhorse

• lock_scan — class-grain only; IS for reads, IX for writes. One real call site: heap scan start.
• lock_object — dispatches on the OID (root / class / instance) and first secures the parent's intention lock.
• Fast-out by subsumption. If a held class lock already covers the row request — class X covering row X, say — lock_object returns LK_GRANTED with no hash lookup, no LK_ENTRY. It's why escalation's remaining 40,000 rows (§worked example) cost nothing. Check: lock_is_class_lock_escalated.

Inside the workhorse — the dispatch tree

• Two questions sort every request — is the resource empty? and do I (the requesting txn) already hold it? — then compatibility decides inside each branch; the small captions name the LK_RES field each decision reads. (Instance requests pass the escalation check before any of this.)

Inside the workhorse — seven paths

E is the OLTP hot path — the class-entry fast path needs no hash lookup and no res_mutex, just hold_mutex and a count bump.
F/G test against the group_mode of others — a transaction cannot conflict with itself.

The dispatch in code — compressed

// lock_internal_perform_lock_object — lock_manager.c
start:      /* re-entered ONLY from the
               sibling branches in D & G */
  find_or_insert (key, &res);            /* lockfree */
  if (res is empty)
    return grant_fresh ();               /* PATH A */
  if (find_mine (res->holder, my_tran))
    goto lock_tran_lk_entry;
  if (compat (lock, res->total_waiters_mode)
      && compat (lock, res->total_holders_mode))
    return grant_immediately ();         /* PATH B */
  if (wait_msecs == ZERO_WAIT)
    return TIMEOUT;                      /* PATH C */
  suspend (); return woken_outcome ();   /* PATH D */

lock_tran_lk_entry:   /* I already hold R */
  new_mode = lock_conv (lock, granted_mode);
  if (new_mode == granted_mode)
    { count++; return GRANTED; }         /* PATH E */
  group = lub_of_OTHER_holders ();
  if (compat (new_mode, group))
    { granted_mode = new_mode;
      return GRANTED; }                  /* PATH F */
  blocked_mode = new_mode;               /* PATH G */
  reposition_per_UPR (); suspend ();

What PATH D leaves behind — the structures

• Continuing the earlier snapshot (T7 holds X, T9 waits): T12's X lands on PATH D — a new LK_ENTRY strictly behind T9 at the FIFO tail, total_waiters_mode = lub(X, X), thread suspended.
• The wake promise: the releaser's thread examines and promotes T12's entry before waking it — so T12 wakes already a holder; otherwise timeout / deadlock victim (§Suspend & resume).
• These waiter→holder relationships are exactly what the deadlock detector later reads off as WFG edges (Part IV).

Lock conversion — the lub rule

• lub = least upper bound. In the lock-mode lattice ordered by strength, lub(A, B) is the smallest mode that satisfies both A and B simultaneously.
• Re-requesting your own lock should upgrade, not deadlock with yourself.
• Rule: granted_mode ← lub(granted_mode, requested_mode)
  • lub(S, IX) = SIX — need both shared and intention-to-write
  • lub(IS, S) = S — S already implies IS
  • lub(S, X) = X — X already implies S
• Implementation: a square table lock_Conv[requested][current] — src/transaction/lock_table.c.
• A holder mid-conversion sets both granted_mode (current) and blocked_mode (target) until the upgrade succeeds — that is PATH G.

Worked example A — self-upgrade with no conflict (PATH F)

T1 reads then writes the same row r. Premise: r belongs to an MVCC-disabled class (a serial, say) — on MVCC tables the read takes no row S and the write jumps straight to X.

-- autocommit off: the transaction starts with the first statement
SELECT * FROM accounts WHERE id = 5;             -- step 1
UPDATE accounts SET balance = 200 WHERE id = 5;  -- step 2
COMMIT;

• The aggregate on LK_RES also flips: total_holders_mode goes S → X. The holder count stays at 1.
• Re-requesting your own lock is not an "ungrant + reacquire". The conversion table replaces that potentially deadlock-prone sequence with one atomic transition.

Why this matters: without the conversion table an upgrade is release-then-reacquire — a window for another txn to slip in and deadlock T1 against itself.

Worked example B — self-upgrade waiting on a conflict (PATH G)

Same code, same MVCC-disabled premise — but another transaction T2 already holds S on row r when T1 begins.

Different from example A: at step 3, T1 is simultaneously a holder (S) and a pending upgrader (to X). T1 never releases its S while waiting — that's why LK_ENTRY carries two mode fields instead of one.

Self-upgrade — worked examples A vs B at a glance

Same LK_ENTRY shape, two different code paths. The conversion table covers both: every defined cell of the matrix has a lub, so there's always a target mode to upgrade to.

The buried upgrader — why holder-list order matters

A blocked upgrader waits inside the holder list (PATH G: it still holds its old mode, so the waiter queue is off-limits) — and on every release the grant pass scans that list front-to-back, stopping at the first plain holder: while (holder && holder->blocked_mode != NULL_LOCK).

Naive insertion — just append. A class-grain timeline; each entry reads granted/blocked (– = NULL_LOCK):

• An upgrader behind any plain holder is invisible to this and every future release — the pass never scans past the zone boundary.
• Position is a correctness property, not bookkeeping. So where exactly must an upgrader sit? → drawn out next, then the rule.

The buried upgrader — the same timeline, drawn

• Panel ② is the bug: the while test fails at plain T5 — T3's eligibility is never even computed.
• Panel ③ is the cost: a grantable upgrade (SIX ∧ IS = ✓) sleeps until timeout or deadlock victimhood.
• The green strip is the real code: UPR moves T3 to the front before it sleeps — granted on the very next release.

Why not just scan the whole list? — the trade behind UPR

A full scan would fix the liveness bug — examine every holder on every release, and position stops mattering. The code chooses otherwise, and the reason is the hot path:

• The classic invariant-vs-scan trade: pay for placement once, on the rare path (the PATH G suspend) — and keep the every-release path constant.
• Full scan would also need continue (not the prefix break) and loses the ->next shortcut — sound only because granted upgrades are repositioned to the zone boundary.
• The holder list's order has exactly one consumer — this scan; everything else is order-independent.

Upgrader Positioning Rule — the placement test

The invariant: keep the holder list shaped [ upgraders… ][ plain holders… ] — then the front-zone scan provably reaches every pending upgrade. lock_position_holder_entry walks the zone with the entry being positioned — call it new — and inserts it before the first available of ta > tb > tc, else appends.

• The grant pass maintains it too: a just-granted upgrade is repositioned back to the zone boundary (lock_grant_blocked_holder) before the pass continues.
• Provenance: upgrades-before-new-waiters is classical (Gray & Reuter; System R / DB2 lineage); the ta/tb/tc test and the name "UPR" are CUBRID's own (lock_manager.c source comment).

ta vs tb — grouping, versus the only order that survives

ta — my target ∧ your target = ✓. We can be granted in the same pass: stand together, and the prefix scan takes the whole group on one release. A batching rule.

tb — we conflict, but one-directionally. Say new = IX→SIX, i = IS→X:  SIX ∧ IS = ✓ — i's held mode doesn't block me — but X ∧ IX = ✗ — my held mode blocks i for as long as I hold. Then the order decides everything:

• The pass grants a compatible prefix and stops at the first failure — so a conflicting pair has exactly one viable order: whoever can be granted while the other still holds goes first.

Suspend & resume — six ways to wake

• Race-free by construction: the waker sets the state before signaling, under the thread-entry mutex.
• lock_suspend asserts no page latch is held — waiting on a lock while holding a latch is the classic ordering deadlock (Appendix A).
• Fast gate: an atomic waiter counter (deadlock_and_timeout_detector) makes an idle 100 ms daemon tick cost one read.
• The three victim rows differ in transaction fate and in who runs the rollback — unpacked in Part IV, right after victim selection.

After the wake — what the resumed thread does

Six states, but only three behaviors — one switch in lock_suspend, one verdict back to the dispatch tree:

// lock_suspend, after the sleep — lock_manager.c
wake_chained_siblings ();    /* tran_next_wait relay */
switch (lockwait_state) {
  case RESUMED:            /* the grant cascade ran */
    return RESUMED;        /* already a holder — done */
  case ABORTED_FIRST:      /* I own the rollback */
    set_error (UNILATERALLY_ABORTED);
    abort_reason = TRAN_ABORT_DUE_DEADLOCK;
    while (sibling_workers (my_tran) > 0)
      { interrupt; sleep (10 ms); }  /* drain them */
    return ABORTED;
  case ABORTED_OTHER:      /* a sibling is FIRST */
  case DEADLOCK_TIMEOUT:   /* txn survives */
  case TIMEOUT:            /* wait_msecs ran out */
    set_error_for_timeout ();
    return DEADLOCK_TIMEOUT or TIMEOUT;
  case INTERRUPT: return INTERRUPT;
}
// back in lock_internal_perform_lock_object
if (ret != RESUMED)        /* entry still parked — */
  perform_unlock_object (entry);  /* detach my own */

Crossing into release — it starts at lock_unlock_object

Everything since the dispatch tree ran inside lock_object — and the acquire side never wakes anyone. Wake-ups belong to the release path, and its entry point decides what is released when:

// lock_unlock_object — src/transaction/lock_manager.c
if (force) {                       // commit / rollback
  lock_internal_perform_unlock_object
    (..., false, true);
  return;
}
if (lock != S_LOCK) return;        // X is commit-bound
switch (logtb_find_isolation (tran_index)) {
  case TRAN_SERIALIZABLE:
  case TRAN_REPEATABLE_READ: return;
  case TRAN_READ_COMMITTED:
    lock_unlock_object_by_isolation (...); break;
}

Inside the release — the grant cascade

All three scopes funnel into lock_internal_perform_unlock_object. Right after the released entry comes off the list, the granting happens — in a fixed order:

• Upgraders before waiters — pass 1 walks the upgrader zone (UPR pays off here); pass 2 walks the FIFO against the updated aggregate, stopping at the first incompatible entry.
• The recompute is O(holders): lub is not invertible — you cannot subtract a mode from an aggregate.

Release internals — count, release_flag, and commit

// lock_internal_perform_unlock_object — src/transaction/lock_manager.c
if (release_flag == false) {
  entry_ptr->count--;
  if (entry_ptr->blocked_mode == NULL_LOCK && entry_ptr->count > 0)
    return;            /* re-entrance guard: most unlock calls exit here */
}

• Every lock_object bumps count; every unlock decrements it. The entry is freed only at zero — a nested caller can't pull the rug from under an outer one.
• lock_unlock_all (commit / rollback; called only by log_manager.c) passes release_flag = true and releases instances → classes → root — leaf-to-root, the reverse of acquisition order.
• An LK_RES is erased from the hash table only when holder, waiter and non2pl lists are all empty; a shadow-only resource stays alive.

Worked example — RC vs RR on the same timeline

Scope. Textbook 2PL story — in CUBRID it applies only to MVCC-disabled classes (serials, etc.). On MVCC user tables, T2 takes no S lock; the same anomaly is resolved by snapshot timing — see cubrid-mvcc.md.

T2 reads twice in one transaction; T1 updates and commits between the reads. What does T2 see at the second read?

Isolation levels at the row — what the code actually varies

• Dispatch is two predicates, not the lock table: mvcc_is_mvcc_disabled_class (4 class kinds) and logtb_check_class_for_rr_isolation_err (3 exempt metadata classes; check sits in locator_sr.c).
• RR ≡ SERIALIZABLE at runtime — every branch tests isolation > TRAN_READ_COMMITTED; SERIALIZABLE is honestly snapshot isolation (TRAN_NO_PHANTOM_READ alias), write skew not prevented.
• Net: isolation moves snapshot timing + one write-time check. The lock manager's X-to-commit discipline never changes.

Lock escalation

// lock_escalate_if_needed — src/transaction/lock_manager.c
if (!lock_check_escalate (th, class_entry, tran_lock))
  return LK_NOTGRANTED;                          // threshold not reached
if (class_entry->granted_mode == IX_LOCK
    || class_entry->granted_mode == SIX_LOCK)
  max_class_lock = X_LOCK;                       // writer  → class X
else
  max_class_lock = S_LOCK;                       // reader  → class S
granted = lock_internal_perform_lock_object (... , max_class_lock,
            LK_FORCE_ZERO_WAIT, &class_entry, NULL);

• Checked on every instance request — one integer compare (ngranules vs the lock_escalation parameter) under hold_mutex, ~100 ns.
• The IS → S, IX/SIX → X choice is a heuristic — counting per-row S vs. X would cost exactly what escalation is trying to save.
• Conditional by design: LK_FORCE_ZERO_WAIT means a contended class lock silently abandons escalation — per-row locking just continues.
• Opt-out: rollback_on_lock_escalation aborts the transaction instead of coarsening its footprint.

Worked example — escalation under bulk DML

A maintenance job runs:

UPDATE accounts SET status = 'archived' WHERE created_at < '2020-01-01';
-- imagine 50,000 rows match

• Memory drops from O(rows touched) to O(1); later checks are one matrix lookup.
• Other transactions wanting any row in accounts now block on the class X for the rest of the txn.
• If another txn holds a conflicting class lock at step 4, the no-wait attempt fails — escalation is abandoned and per-row locking continues.

Deadlock — Waits-For Graph

• Each detection run derives edges (LK_WFG_EDGE) from the lock table — built fresh per scan, not maintained online at wait time.
• lock_detect_local_deadlock walks the graph with DFS; a back-edge to a node on the path is a cycle.
• "Local" — distributed deadlocks are not this detector's problem; they fall back to per-request timeout.

Detection — three gates, five phases

• The WFG is rebuilt from scratch on every run — zero bookkeeping on the lock/unlock hot path; the scan costs O(active resources), at most once per second (lock_deadlock_detect_interval).
• Safety net: 60 consecutive victim-less runs (~6 s) force-time-out one suspended thread to break undetectable hangs.

WFG in code — the detector's own structures

// lock_manager.c — TWFG: rebuilt into lk_Gl on every detection run
struct lk_WFG_node {              // one slot per transaction
  int   first_edge;               // head of my outgoing edges (-1 = none)
  int   current, ancestor;        // DFS cursor + path parent (phase 3)
  INT64 thrd_wait_stime;          // when this txn started waiting
  int   tran_edge_seq_num;        // stale-edge filter
  bool  checked_by_deadlock_detector, DL_victim;
};
struct lk_WFG_edge {              // one "waits-for" arrow
  int   to_tran_index;            // the txn I wait for
  int   holder_flag;              // target holds? → victim criterion #1
  int   next;                     // next edge of the same from-node
  int   edge_seq_num;   INT64 edge_wait_stime;
  LK_ENTRY *holder, *waiter;      // evidence back in the lock table
};

• An adjacency list in two flat arrays: lk_Gl.TWFG_node[tran_index] + one shared TWFG_edge[] pool — edges chain by index (first_edge → next), not by pointer.
• Nodes are transactions, not threads or resources; edge storage grows in tiers — 200 (static) → 1,000 → MAX_NTRANS² (malloc) — read-only workloads never allocate.

Detection in compressed code — one run, five phases

// lock_detect_local_deadlock — lock_manager.c
/* 1 reset */
for (k : every txn slot)
  TWFG_node[k] = { first_edge: -1, checked: true };
/* 2 build */
for (res : every LK_RES)          /* hash iterate */
  for ((blocked, blocking) : holder×holder,
        waiter×holder, waiter×waiter pairs)
    if (!compat (blocked_mode, their mode))
      lock_add_WFG_edge (from, to, holder_flag);
/* 3 DFS */
for (k : every txn)  walk current / ancestor;
  reach a node already on my path → CYCLE
/* 4–5 victims */
lock_select_deadlock_victim ();   /* six criteria */
lock_wakeup_deadlock_victim_* (); /* abort | timeout */

Building the graph — three kinds of edges

• Every (blocked, blocking) pair on every resource becomes one directed LK_WFG_EDGE; the holder_flag on each edge feeds victim criterion #1.
• Stale edges (their txn committed mid-scan) are filtered during DFS by sequence-number checks; a cycle containing one is discarded as false.

Victim selection — six tie-breakers, in order

1. Must be a lock holder somewhere in the cycle (holder_flag) — only a holder's rollback frees what the cycle waits on; aborting a pure waiter breaks nothing.
2. Must be an active transaction — one already committing / aborting is exiting anyway; it cannot be aborted again.
3. Prefer one without deadlock priority — protected transactions survive.
4. Prefer fewer log records written — the cheapest rollback.
5. Prefer one with a finite timeout — that application already expects retries.
6. Prefer the youngest (highest tranid) — the least work thrown away, and elders keep their progress instead of being re-victimized forever.

• Resolution is two-mode: finite-wait_msecs victims wake as LOCK_RESUMED_DEADLOCK_TIMEOUT (retryable); infinite-wait victims wake as LOCK_RESUMED_ABORTED_* (rollback).
• Not "most recently blocked" — earlier revisions of this deck (and the high-level doc) inferred that from insertion order; the detail doc's walk of lock_select_deadlock_victim settles it.

Resolving the victim — why three wake states

One victim, three possible wake states. The differences: what happens to the transaction, and who does the work:

• The TIMEOUT / ABORTED split is the victim's wait_msecs: finite → that application already handles timeout-shaped failures, so the transaction survives and may retry; infinite → abort is the only exit.
• FIRST / OTHER exists because one transaction can have several threads parked on locks at once — the detector wakes them all, but exactly one is "charged of the transaction abortion" (the source comment); the rest are notified as timeouts so the rollback never runs twice.

Worked example — two transactions, two rows

Setup: accounts (id, balance), initial A.balance = 1000, B.balance = 1000. Two sessions start at the same time:

T1 transfers from A to B; T2 transfers from B to A. The schedule depends on how the scheduler interleaves the two — and one of them is unlucky.

Worked example — interleaving creates the cycle

• After t = 4, both transactions are in LOCK_SUSPENDED.
• Neither will progress without external intervention — the lock table now encodes a cycle of length 2, waiting for the next detection run to find it.

Per-request timeout would eventually break this, but minutes of wasted wait — the detector resolves it within its one-second scan interval.

Worked example — the cycle, visualized

• Left: the concrete lock table — two LK_RES records, each with a holder and a waiter.
• Right: the abstract WFG — one node per transaction, one waiter→holder edge per blocking relationship (edge category (b)).
• The detector never inspects rows. It sweeps the lock table once to build the graph, then walks only the graph.

Worked example — the detector resolves it

A daemon tick passes the gates (two suspended threads; interval up):

1. Build. Sweep the lock table: row A yields edge T2 → T1; row B yields edge T1 → T2.
2. DFS. Start at T1 → follow to T2 → back-edge to T1, which is on the DFS path → cycle found.
3. Victim. Both are holders, both active, no deadlock priority set, log-record counts tie at one update each — the youngest tie-breaker picks T2 (it started later).
4. Wake. With the default infinite wait, T2 resumes as LOCK_RESUMED_ABORTED_FIRST → rollback releases its X on B. (With a finite wait_msecs it would get the retryable DEADLOCK_TIMEOUT instead.)
5. Cascade. The release grants T1's pending X on B (§grant cascade); T1 runs the rest of its statements and commits.

No lock is ever taken away from a running txn. The loser pays a rollback; the winner only notices a bit of extra wait.

Worked example — a three-transaction cycle

Each transaction grabs one row, then reaches for the next — a circular chain.

• DFS from T1 walks T1→T2→T3, back-edge to T1 — cycle at depth 3. Victim = T3: criteria 1–5 tie; youngest decides.
• T3 aborts → R3 freed → T2 wakes → R2 freed → T1 wakes — a chain of grant cascades.

Special paths — instant probe

• "Would this lock be granted right now?" — the same dual-aggregate compatibility test, with zero state created.
• User & workload — and why: scan_manager.c, row visits during heap / index scans. A real lock_object per visited row costs a hash find_or_insert plus list mutation under res_mutex — per row — yet most rows are uncontended. So the scan probes read-only first and falls back to lock_object only on conflict: the common case never pays for a lock entry.

Special paths — composite lock

• User & workload — and why: query_executor.c, bulk DELETE / UPDATE plans (carried in the XASL). Acquiring each row's X mid-scan invites deadlocks with concurrent transactions and threads the suspends through the scan loop — so the scan only collects OIDs and all X locks land in one batch at finalize (detail ch. 9).
• Built-in escalation: if a class's collected-OID count reaches the lock_escalation threshold, collection stops and finalize takes class X instead.

Special paths — NON2PL, shadows for early-released S locks

• A shadow never blocks anyone — it is bookkeeping, not a lock mode in the matrix sense.
• Why it exists: RC's statement-end S release is a deliberate 2PL violation — afterwards the client still holds a cached copy it no longer protects. The shadow records that fact, so a later conflicting grant can mark the copy stale (phase 2) and decache it at the next fetch (phase 3).
• User & workload: serial.c — serial-row access under RC (§caller map: the main NON2PL exerciser). Predates MVCC, when every RC read released early; today only the MVCC-disabled niche remains.

Special paths — the rest of the API surface

None of these introduce new machinery — every one bottoms out in lock_internal_perform_lock_object.

What's not on a slide — read next

The two analysis docs carry what a slide can't:

Doc	What's there
cubrid-lock-manager.md	design intent, theory code mapping, open questions, position hints
…-detail.md ch. 1–2	every struct field; boot, the hash function, lockfree integration
ch. 3–4	paths A–G line-by-line; UPR deep dive (ta / tb / tc candidates)
ch. 5–7	NON2PL & instant-lock internals; suspend / timeout machinery
ch. 8–9	WFG staleness checks, victim-selection code; composite / demote / subclass

Both docs keep position-hint tables with line numbers as of their updated: dates.
When they drift: git grep -n '<symbol>' src/transaction/.

Beyond CUBRID — research frontiers

CUBRID's dial position: textbook 2PL + MGL + WFG detection. A well-defended point.

Appendix A — Lock vs Latch, side by side

Two words that sound alike. Same DBMS, completely different machines.

Database Internals ch. 5's first hard rule: don't conflate them.

Appendix A — Lock vs Latch, in code (CUBRID heap insert)

PGBUF_LATCH page (X)              ← physical: nobody else may mutate this page
allocate slot, write record       ← page is now correct in memory
lock_object on (page, slot) OID   ← logical: claim transactional visibility
UNLATCH page                      ← physical exclusion ends here

... continue with the rest of the txn (latch released, lock retained) ...

at commit: lock_unlock_object     ← logical lock finally released

• Page latch lives for microseconds — only while the bytes mutate.
• Row lock lives for minutes to hours — until the txn commits.
• The two timescales differ by orders of magnitude. Conflating them is a structural bug:
  • holding a lock during a page-level critical section serializes the entire workload through that page.
  • holding a latch across a network round-trip serializes the entire workload through that thread.
• B-tree split uses latches only — no transactional visibility implications.

Appendix B — the lock-table hash is not a modulo

// lock_get_hash_value — src/transaction/lock_manager.c
next_base_slotid = 2;
while (next_base_slotid <= slotid)
  next_base_slotid *= 2;
addr = pageid + (htsize / next_base_slotid)
              * (2 * slotid - next_base_slotid + 1);
return addr % htsize;

• Consecutive slots of one heap page are strided apart (van Emde Boas-style), so a scan locking rows in order hits widely separated buckets — no chain contention between parallel scans.
• slotid ≤ 0 (index last-key OIDs use -1) falls back to a simple pageid - slotid.

Appendix C — Q&A: how does release detach an entry?

"When a transaction commits, does it search the lock table for its entries?" — No. Commit walks its own hold lists and calls unlock with the entry pointer already in hand (§dual-view). The only walk left is splicing the entry out of the resource's holder list:

// lock_internal_perform_unlock_object — src/transaction/lock_manager.c
/* resource-side list is singly linked — find prev to splice */
prev = NULL;  curr = res_ptr->holder;
while (curr != NULL) {
  if (curr->tran_index == tran_index) break;
  prev = curr;  curr = curr->next;
}
if (prev == NULL) res_ptr->holder = curr->next;
else              prev->next = curr->next;