CUBRID Extendible Hash — Code-Level Deep Dive

Where this document fits: The high-level analysis cubrid-extendible-hash.md covers design intent and theoretical background. This document traces every branch and field at the code level. Each chapter is self-contained, but reading in order follows a single key from hash derivation through directory lookup, bucket operations, and split-driven directory doubling.

Contents:

Ch	Title	Status
1	Data-Structure Map	✅
2	File Creation and Memory Layout	✅
3	Hashing and Directory Addressing	✅
4	Searching Inside a Bucket	✅
5	Inserting Into a Non-Full Bucket	✅
6	Splitting a Full Bucket and Raising Local Depth	✅
7	Doubling the Directory and Connecting Bucket Pointers	✅
8	Deleting a Key and Merging Buckets	✅
9	Shrinking the Directory	✅
10	Edge Paths Recovery and Concurrency	✅

---

Chapter 1: Data-Structure Map

This chapter answers one question: what exactly is on disk for an extendible-hash file, and what is every field for? It is the inventory of structs, the macros that interpret their bytes, the invariants the rest of the code assumes, and the one function mapping a logical pointer index to a physical (page, offset) — ehash_dir_locate.

Fagin’s theory, the doubling intuition, and the four CUBRID call sites live in the high-level companion cubrid-extendible-hash.md and are not repeated here. Symbols come from src/storage/extendible_hash.c, src/storage/storage_common.h, and src/compat/dbtype_def.h.

1.1 The on-disk handle: EHID, VFID, VPID

Everything starts from a 12-byte handle, declared in storage_common.h:

// ehid -- src/storage/storage_common.h
struct ehid
{
  VFID vfid;     /* Volume and Directory file identifier */
  INT32 pageid;  /* The first (root) page of the directory */
};

EHID is not itself a file id — it is (directory-file, root-page-of-that-file). The embedded VFID names the directory file; pageid is the page within it where the header lives. The bucket file is reached through a field inside the header (§1.2), not from the EHID.

// vpid / vfid -- src/compat/dbtype_def.h
struct vpid { int32_t pageid; short volid; };  /* a page: page# + which volume */
struct vfid { int32_t fileid; short volid; };  /* a file: file# + which volume */

Struct	Field	Role	Why it exists
EHID	vfid	VFID of the directory file	Re-opens the directory file by id; the root page lives in this file
EHID	pageid	Page number of the directory root page within vfid	The single entry point: fix this page to reach the header at offset 0
VFID	fileid	File number within a volume	Identifies a file to the file manager
VFID	volid	Volume the file lives on	(volid, fileid) is globally unique
VPID	pageid	Page number within a volume	Identifies one page for the page buffer
VPID	volid	Volume the page lives on	(volid, pageid) is the global page address pgbuf_fix uses

Invariant — the EHID is the only durable root. Every traversal begins by fixing ehid->vfid page ehid->pageid; nothing in the file points back. Callers persist the EHID themselves. Lose it and the file is orphaned though its pages survive.

1.2 The directory header: EHASH_DIR_HEADER

The first directory page opens with a fixed header; directory pointers fill the rest of that page and all subsequent pages.

// ehash_dir_header -- src/storage/extendible_hash.c
struct ehash_dir_header
{
  /* Fields should be ordered according to their sizes */
  VFID bucket_file;
  VFID overflow_file;
  int local_depth_count[EHASH_HASH_KEY_BITS + 1];
  DB_TYPE key_type;
  short depth;
  char alignment;
};

EHASH_HASH_KEY_BITS is sizeof(EHASH_HASH_KEY) * 8 with typedef unsigned int EHASH_HASH_KEY, so it is 32 on the only supported configuration (the source carries a TODO: ~0: M2 64-bit caveat on the masking macros). local_depth_count therefore has 33 entries, indexed 0..32.

Field	Role	Why it exists
bucket_file	VFID of the file holding all (non-overflow) bucket pages	Buckets live in their own file so directory and buckets grow independently; dir entries store VPIDs into it
overflow_file	VFID of the file holding overflow bucket pages	Long string keys and rare collisions spill into overflow pages in their own file
local_depth_count[i]	Histogram: how many buckets currently have local depth = i	O(1) shrink oracle; maintained incrementally by ehash_adjust_local_depth
key_type	DB_TYPE of the hashed keys (e.g. DB_TYPE_STRING, DB_TYPE_OBJECT)	Selects hash function, comparison, slot encoding; uniform across all buckets
depth	Global depth d of the directory	Presents 2^depth logical pointers; FIND_OFFSET masks exactly depth leading bits (§1.5)
alignment	Slot alignment used on bucket pages	Records on the slotted bucket pages align here; fixed at create time, replayed during recovery

Fields are ordered largest-to-smallest so the struct packs without internal padding, then rounded up by EHASH_DIR_HEADER_SIZE (§1.4).

Invariant — local_depth_count is a faithful histogram, and global depth dominates every local depth. local_depth_count[i] counts buckets whose EHASH_BUCKET_HEADER.local_depth == i; every split/merge routes its depth change through ehash_adjust_local_depth (decrement old, increment new, one logged action). Separately, every bucket has local_depth <= header.depth: a split that would exceed depth must first double the directory (Chapters 6–7). A drifted histogram reads the wrong shrink width; a local depth past global depth aliases the wrong bucket.

1.3 Directory entries and bucket headers: EHASH_DIR_RECORD, EHASH_BUCKET_HEADER

A directory entry is just a bucket pointer:

// ehash_dir_record -- src/storage/extendible_hash.c
struct ehash_dir_record { VPID bucket_vpid; };  /* bucket pointer */

Struct	Field	Role	Why it exists
EHASH_DIR_RECORD	bucket_vpid	VPID of the bucket page this slot points to	The directory is an array of these; 2^depth of them, possibly many pointing at the same bucket — that is how local depth < global depth is represented

A bucket at local depth L is referenced by exactly 2^(depth - L) consecutive directory slots holding the same bucket_vpid. Each bucket page begins with a one-byte header:

// ehash_bucket_header -- src/storage/extendible_hash.c
struct ehash_bucket_header { char local_depth; };  /* The local depth of the bucket */

Struct	Field	Role	Why it exists
EHASH_BUCKET_HEADER	local_depth	Local depth of this bucket (leading pseudo-key bits it discriminates on)	Stored in slot 0 of the bucket’s slotted page; split reads it to set the sibling’s depth and compute which directory slots to re-point

Invariant — the bucket header occupies slot 0. The local_depth byte is record slot 0 of the slotted bucket page; key/value records occupy slots 1..n. Bucket scans (Chapter 4) start at slot 1; split/merge read/write the depth via slot 0. Writing data into slot 0 destroys the local depth and every directory-width computation derived from it.

1.4 Page geometry macros

These macros translate the structs above into page layout. DB_PAGESIZE is the configured page size (commonly 16 KB). The two field-bearing macros are shown verbatim; the four derived counts/offsets are summarized in the table below.

// EHASH_DIR_HEADER_SIZE / EHASH_MAX_STRING_SIZE -- src/storage/extendible_hash.c
#define EHASH_DIR_HEADER_SIZE \
  ((ssize_t) (((sizeof(EHASH_DIR_HEADER) + sizeof(int) - 1 ) / sizeof(int) ) * sizeof(int)))
  /* <- round header size up to a multiple of sizeof(int) (4) */
#define EHASH_MAX_STRING_SIZE \
  (DB_PAGESIZE - (SSIZEOF(EHASH_BUCKET_HEADER) + 16))   /* <- 16 = two slot indices */

Macro	Value	Why it exists
EHASH_DIR_HEADER_SIZE	sizeof(EHASH_DIR_HEADER) rounded up to a 4-byte boundary	Page-0 pointers begin at this offset; keeps VPID entries int-aligned
EHASH_MAX_STRING_SIZE	DB_PAGESIZE - (1 + 16)	Longest inline string key; longer keys go to overflow. 16 reserves two slot entries
EHASH_NUM_FIRST_PAGES	(DB_PAGESIZE - EHASH_DIR_HEADER_SIZE) / sizeof(VPID)	Pointers fitting on the first page (shared with the header)
EHASH_NUM_NON_FIRST_PAGES	DB_PAGESIZE / sizeof(VPID)	Pointers fitting on every later page (no header)

Two companion macros, EHASH_LAST_OFFSET_IN_FIRST_PAGE and EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE, give the final-pointer byte offset on each page kind for the page-to-page walk in expand/shrink.

Invariant — the directory is one logical array striped across pages. Logically EHASH_DIR_RECORD dir[2^depth]. The first EHASH_NUM_FIRST_PAGES entries live on page 0 after the header; each later page holds EHASH_NUM_NON_FIRST_PAGES. No entry straddles a page boundary — both counts divide whole VPIDs into the available bytes, leaving a < sizeof(VPID) leftover as padding. Every consumer needing entry k calls ehash_dir_locate (§1.6); nothing assumes a flat address.

1.5 Bit-field macros — extracting a left-adjusted prefix

The pseudo-key is a 32-bit unsigned int; the directory uses its leading depth bits, with positions numbered 1..32 from the left (MSB). All extraction funnels through GETBITS:

// GETBITS -- src/storage/extendible_hash.c
#define GETBITS(value, pos, n) \
  ( ((value) >> ( EHASH_HASH_KEY_BITS - (pos) - (n) + 1)) & (~(~0UL << (n))) )
  /* shift the wanted field down to bit 0, then mask off the low n bits */

~(~0UL << n) builds an n-bit low mask; the shift 32 - pos - n + 1 slides the field at pos, width n, down to bit 0 (unsigned value, so the right shift zero-fills). Worked example: value = 0xC0000000, pos = 1, n = 3 → shift 29, 0xC0000000 >> 29 = 6 — the directory index in a depth-3 directory.

// FIND_OFFSET / GETBIT / SETBIT / CLEARBIT -- src/storage/extendible_hash.c
#define FIND_OFFSET(hash_key, depth) (GETBITS((hash_key), 1, (depth)))         /* leading `depth` bits */
#define GETBIT(word, pos)            (GETBITS((word), (pos), 1))               /* one bit at pos */
#define SETBIT(word,  pos) ( (word) | (1 << (EHASH_HASH_KEY_BITS - (pos))) )   /* set bit pos to 1 */
#define CLEARBIT(word, pos) ( (word) & ~(1 << (EHASH_HASH_KEY_BITS - (pos))) ) /* clear bit pos to 0 */

Macro	Returns / effect	Why it exists
FIND_OFFSET(h, d)	Integer from the leading d bits of h	The directory index for pseudo-key h at depth d — the addressing function
GETBIT(w, pos)	The single bit at pos (0 or 1)	At split time, picks which sibling a record goes to (bit just past old local depth)
SETBIT(w, pos)	w with bit pos forced to 1	Sibling directory index with a 1 in the discriminating bit
CLEARBIT(w, pos)	w with bit pos forced to 0	Sibling index with a 0; (CLEARBIT, SETBIT) is the two-sibling pair

Invariant — leading bits, not trailing. CUBRID extracts the high-order depth bits (left-adjusted, counted from 1 at the MSB) — the opposite of textbooks that mask low bits. Every macro hard-codes EHASH_HASH_KEY_BITS - pos; mixing in a low-bit mask would send one key to two slots and lose data. Chapter 3 builds addressing on these macros.

1.6 Mapping a pointer index to a page: ehash_dir_locate

ehash_dir_locate is the function form of the “directory is one striped array” invariant: it takes a logical pointer index in *out_offset_p and overwrites the two outputs with the physical (page_no, byte_offset):

// ehash_dir_locate -- src/storage/extendible_hash.c
static void
ehash_dir_locate (int *out_page_no_p, int *out_offset_p)
{
  int page_no, offset;
  offset = *out_offset_p;                          /* <- input: logical pointer index */
  if (offset < EHASH_NUM_FIRST_PAGES)
    {                                               /* branch A: page 0, after the header */
      offset = offset * sizeof (EHASH_DIR_RECORD) + EHASH_DIR_HEADER_SIZE;
      page_no = 0;
    }
  else                                              /* branch B: a later page, no header */
    {
      offset -= EHASH_NUM_FIRST_PAGES;
      page_no = offset / EHASH_NUM_NON_FIRST_PAGES + 1;
      offset = (offset % EHASH_NUM_NON_FIRST_PAGES) * sizeof (EHASH_DIR_RECORD);
    }
  *out_page_no_p = page_no;
  *out_offset_p = offset;
}

Exactly two branches (see Figure 1-1), split by whether the index fits on the header-sharing first page. There is no error branch and no early return: the function is total over non-negative indices and never fails — callers pass a count rather than an index to learn how many pages span that many entries. It is the canonical mapping, used across create, insert, expand, shrink, and dump.

flowchart TD
  A["ehash_dir_locate(&page_no, &offset)\ninput: offset = logical pointer index"] --> B{"offset < EHASH_NUM_FIRST_PAGES ?"}
  B -- "yes: branch A, page 0" --> C["offset = offset * sizeof(VPID) + EHASH_DIR_HEADER_SIZE\npage_no = 0"]
  B -- "no: branch B, later page" --> D["offset -= EHASH_NUM_FIRST_PAGES"]
  D --> E["page_no = offset / EHASH_NUM_NON_FIRST_PAGES + 1\noffset = (offset % EHASH_NUM_NON_FIRST_PAGES) * sizeof(VPID)"]
  C --> F["write *out_page_no_p, *out_offset_p"]
  E --> F

Figure 1-1. The two branches of ehash_dir_locate. Both paths converge on the same output write; there is no failure path.

1.7 The recovery payload: EHASH_REPETITION

Directory expansion writes the same bucket VPID into the 2^(depth-L) consecutive slots a local-depth-L bucket occupies. Logging each write individually would bloat the log, so the redo record carries a run-length-encoded payload:

// ehash_repetition -- src/storage/extendible_hash.c
struct ehash_repetition
{
  /* The "vpid" is repeated "count" times */
  VPID vpid;
  int count;
};

Struct	Field	Role	Why it exists
EHASH_REPETITION	vpid	The bucket pointer to be written	One value covers a whole run of identical directory slots
EHASH_REPETITION	count	How many consecutive slots get this vpid	RLE run length; lets one small record reconstruct the run on redo

This is the only struct in the module that exists purely for recovery. The forward-log writer (ehash_connect_bucket) and its idempotent redo handler (ehash_rv_connect_bucket_redo) are traced in Chapter 10.

1.8 Result enums: EHASH_RESULT and EH_SEARCH

EHASH_RESULT is the internal seven-valued status threaded through insert/split/merge:

// EHASH_RESULT -- src/storage/extendible_hash.c
typedef enum
{
  EHASH_SUCCESSFUL_COMPLETION,
  EHASH_BUCKET_FULL,        /* Bucket full condition; used in insertion */
  EHASH_BUCKET_UNDERFLOW,   /* Bucket underflow condition; used in deletion */
  EHASH_BUCKET_EMPTY,       /* Bucket empty condition; used in deletion */
  EHASH_FULL_SIBLING_BUCKET,
  EHASH_NO_SIBLING_BUCKET,
  EHASH_ERROR_OCCURRED
} EHASH_RESULT;

Value	Meaning
EHASH_SUCCESSFUL_COMPLETION	Operation finished, nothing further needed
EHASH_BUCKET_FULL	The target bucket cannot hold the new record (drives the split path)
EHASH_BUCKET_UNDERFLOW	After delete, occupancy fell below the underflow threshold
EHASH_BUCKET_EMPTY	After delete, the bucket holds no data records (stronger underflow case)
EHASH_FULL_SIBLING_BUCKET	Merge candidate’s sibling is too full to absorb this bucket
EHASH_NO_SIBLING_BUCKET	The sibling slot does not point at a distinct mergeable bucket
EHASH_ERROR_OCCURRED	An error (latch, I/O, allocation) interrupted the operation

EH_SEARCH is the public three-valued result of ehash_search, declared in storage_common.h:

// EH_SEARCH -- src/storage/storage_common.h
typedef enum { EH_KEY_FOUND, EH_KEY_NOTFOUND, EH_ERROR_OCCURRED } EH_SEARCH;

Value	Meaning
EH_KEY_FOUND	Key located; the OID was copied into the caller’s value_ptr
EH_KEY_NOTFOUND	Key absent from its bucket; value_ptr untouched
EH_ERROR_OCCURRED	Search aborted on error before a definitive answer

EHASH_RESULT never escapes the module; only EH_SEARCH (and the OID * returns of insert/delete) cross the API boundary, keeping the public contract a clean found/not-found/error triple.

1.9 Pointer-relationship panorama

Figure 1-2. Pointer panorama. The EHID is the only externally-held root; page 0’s header holds the bucket and overflow file ids; dir[] is striped across directory pages and each bucket_vpid points into the bucket file. Several dir[] entries may share one bucket (local depth < global depth).

1.10 Chapter summary — key takeaways

1. EHID = (directory VFID, root pageid) is the sole durable handle. The structure has no back-pointer to it; every traversal fixes that root page first.
2. The directory header (EHASH_DIR_HEADER) holds the two file ids, the depth histogram, the key type, the global depth, and the bucket alignment. bucket_file/overflow_file are reached through the header, never from the EHID; local_depth_count[0..32] is an O(1) shrink oracle maintained incrementally by ehash_adjust_local_depth.
3. Two depth invariants govern everything: every bucket’s local_depth <= header.depth, and local_depth_count is a faithful histogram of those depths.
4. The directory is one logical 2^depth array striped across pages; ehash_dir_locate is the canonical, never-failing index-to-(page, offset) map (branch A = page 0, branch B = later pages).
5. Addressing uses the leading (high-order) depth bits of a 32-bit unsigned pseudo-key, extracted by GETBITS/FIND_OFFSET; GETBIT/SETBIT/CLEARBIT compute the two-sibling pair at split/merge time.
6. A bucket page keeps its local depth in slot 0 (EHASH_BUCKET_HEADER); several directory entries sharing one bucket page is the representation of local depth below global depth.
7. EHASH_REPETITION (vpid, count) is the RLE recovery payload (forward-log/redo mechanics in Chapter 10). EHASH_RESULT (seven values) stays internal; only the three-valued EH_SEARCH crosses the public API.

Chapter 2: File Creation and Memory Layout

This chapter answers: given the structures from Chapter 1, how is a brand-new hash file bootstrapped into the initial one-bucket state? We trace xehash_create -> ehash_create_helper branch by branch and establish the starting invariant later chapters rely on (Ch 6–8). For the meaning of extendible hashing see the companion cubrid-extendible-hash.md (## Algorithm, ## Directory and Buckets); the /* Branch X-no */ annotations in 2.5–2.10 carry the control flow.

2.1 The two files and their descriptor

A hash table is two numerable files on one volume: a bucket file (FILE_EXTENDIBLE_HASH) and a directory file (FILE_EXTENDIBLE_HASH_DIRECTORY), both stamped with the same FILE_EHASH_DES descriptor — the only application-specific payload in the header.

// struct file_ehash_des -- src/storage/file_manager.h
struct file_ehash_des
{
  OID class_oid;                /* class the index belongs to, or NULL OID */
  int attr_id;                  /* attribute id within that class */
};

Field	Role	Why it exists
class_oid	OID of the class the index serves; NULL OID if none	Makes a stray hash file self-describing
attr_id	Indexed attribute within class_oid	Disambiguates indexes on one class

FILE_EHASH_DES is one arm of union file_descriptors (fixed FILE_DESCRIPTORS_SIZE = 64 bytes). The same descriptor goes to both file_create_ehash and file_create_ehash_dir, so the file type, not the descriptor, tells bucket from directory. The caller keeps only the EHID {directory VFID, directory root pageid}; everything else is reachable by fixing the directory root (Figure 2-1).

flowchart TD
  EHID["EHID (caller)<br/>vfid=dir VFID, pageid=dir root"]
  DIRH["EHASH_DIR_HEADER (dir pg 0)<br/>depth=0, bucket_file, ldc[0]=1"]
  REC["EHASH_DIR_RECORD[0]<br/>bucket_vpid -> bucket pg 0"]
  BKT["bucket pg 0<br/>slot 0 = header, local_depth=0"]
  EHID --> DIRH --> REC --> BKT
  DIRH -. "bucket_file VFID" .-> BKT

Figure 2-1. Object graph produced by ehash_create_helper.

2.2 xehash_create — the thin public wrapper

xehash_create is the server entry point; it forwards verbatim to ehash_create_helper (thread_p, ehid_p, key_type, exp_num_entries, class_oid_p, attr_id, is_tmp). Inbound contract: the caller must already have set ehid_p->vfid.volid (target volume); all other EHID fields are output. The split is historical; only the helper carries logic.

2.3 ehash_get_key_size and the DB_TYPE_STRING sentinel

The helper first resolves the per-key byte budget used for alignment and the page estimate:

// ehash_get_key_size -- src/storage/extendible_hash.c
case DB_TYPE_STRING:
  key_size = 1;             /* Size of each key will vary */
  break;
case DB_TYPE_OBJECT:
  key_size = sizeof (OID);
  break;
#if defined (ENABLE_UNUSED_FUNCTION)
case DB_TYPE_DOUBLE:   key_size = sizeof (double);  break;
// ... condensed: FLOAT, INTEGER, BIGINT, SHORT, DATE/TIME/TIMESTAMP, DATETIME, MONETARY ...
#endif
default:
  er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_INVALID_KEY_TYPE, 1, key_type);
  key_size = -1;            /* <- only error return */
  break;

Two facts a modifier must hold: (1) DB_TYPE_STRING returns 1, not a real size — strings are variable-length (source comment “Size of each key will vary”); 1 is the alignment-minimum placeholder, the real string budget is computed separately (2.5), and treating 1 as the key width is the classic bug. (2) Fixed-width branches are walled off by ENABLE_UNUSED_FUNCTION — in a stock build the only reachable non-error cases are DB_TYPE_STRING and DB_TYPE_OBJECT; everything else hits default, returns -1.

INVARIANT — key type is STRING or OID. Every reachable path assumes key_type in {DB_TYPE_STRING, DB_TYPE_OBJECT}; ehash_create_helper asserts this in debug (assert (key_type == DB_TYPE_STRING || key_type == DB_TYPE_OBJECT)), and in release the -1 return aborts creation (2.4, branch B). If violated (enable ENABLE_UNUSED_FUNCTION, pass DB_TYPE_DOUBLE), the fixed-width path runs and the 20-byte string allowance never applies — the page estimate drifts, correctness does not.

2.4 ehash_create_helper — branch-complete walkthrough

Branches are annotated inline in 2.5–2.10. Branches A, B, J (the first file_create_ehash) return NULL directly with nothing to undo; every failure after the first file_alloc (L, P, Q, R) funnels through the single goto exit_on_error (2.10). The two branches without an excerpt elsewhere: A — null ehid: if (ehid_p == NULL) return NULL;, before any allocation; descriptor fill (A->B) copies class_oid when supplied else OID_SET_NULL, attr_id verbatim, reusing this ehdes for both file-create calls; B — bad key size: if (key_size < 0) return NULL; after ehash_get_key_size already er_set the error.

2.5 The exp_num_entries -> page-count estimate

The estimate only improves disk locality; it does not affect correctness:

// ehash_create_helper -- src/storage/extendible_hash.c
if (exp_num_entries < 0)
  exp_bucket_pages = 1;                                               /* <- one-page collapse */
else
  {
    if (key_type == DB_TYPE_STRING)
      exp_bucket_pages = exp_num_entries * (20 + sizeof (OID) + 4);   /* <- string budget */
    else
      exp_bucket_pages = exp_num_entries * (key_size + sizeof (OID) + 4); /* <- OID budget */
    exp_bucket_pages = CEIL_PTVDIV (exp_bucket_pages, DB_PAGESIZE);
  }

The string budget ignores the 1 sentinel (20-byte allowance + OID value + 4 slot bytes); the OID budget is key_size + sizeof(OID) + 4. The directory estimate (2.9) collapses identically.

2.6 Alignment computation

Alignment pads bucket-page slots so a key (or OID value) lands on a natural boundary:

// ehash_create_helper -- src/storage/extendible_hash.c
if (SSIZEOF (value.pageid) >= key_size)        /* <- value.pageid is an OID field */
  alignment = sizeof (value.pageid);
else
  alignment = (char) key_size;
if (alignment > SSIZEOF (int))
  alignment = sizeof (int);                    /* <- hard cap at sizeof(int) */

Both reachable key types settle to sizeof(int): for STRING (key_size == 1) pageid wins; for OBJECT the cap fires. This alignment feeds the bucket init data (2.7) and directory header (2.9).

2.7 Bucket file and bucket page 0

The bucket file is created first; note the volid handoff:

// ehash_create_helper -- src/storage/extendible_hash.c
bucket_vfid.volid = ehid_p->vfid.volid;        /* <- bucket borrows the caller's target volid */
if (file_create_ehash (thread_p, exp_bucket_pages, is_tmp, &ehdes, &bucket_vfid) != NO_ERROR)
  { ASSERT_ERROR (); return NULL; }            /* Branch J-no: clean, nothing allocated yet */

Counter-intuitive volid ordering. The bucket file claims ehid_p->vfid.volid first; only later does dir_vfid.volid = bucket_vfid.volid (2.9) pull the directory onto the same volume. Though the EHID ultimately holds the directory VFID, the volume id flows caller -> bucket -> directory; the ehid->vfid overwrite is the last assignment (2.10).

file_create_ehash shapes the generic file_create (..., FILE_EXTENDIBLE_HASH, ..., is_tmp, true, vfid); the trailing true is is_numerable (ordinal-addressable pages, used by ehash_fix_nth_page, 2.10). Page 0 is then allocated with an init callback, formatting it atomically:

// ehash_create_helper -- src/storage/extendible_hash.c
init_bucket_data[0] = alignment;  init_bucket_data[1] = 0;  init_bucket_data[2] = is_tmp;
/* triple {alignment, depth, is_temp}; depth HARD-CODED 0 -> seed local depth */
if (file_alloc (thread_p, &bucket_vfid, ehash_initialize_bucket_new_page, init_bucket_data, &bucket_vpid, NULL)
    != NO_ERROR)
  { ASSERT_ERROR (); goto exit_on_error; }      /* Branch L-no */

2.8 ehash_initialize_bucket_new_page — the bucket init callback

file_alloc invokes this once the new page frame is fixed — decode args, format the page, log permanent files. The header it lays down is the one-byte EHASH_BUCKET_HEADER:

// struct ehash_bucket_header -- src/storage/extendible_hash.c
struct ehash_bucket_header
{
  char local_depth;             /* The local depth of the bucket */
};

Field	Role	Why it exists
local_depth	Number of hash-key bits this bucket discriminates on	Split/merge (Ch 6, 8) compare it against the directory’s global depth to decide doubling vs. local split

// ehash_initialize_bucket_new_page -- src/storage/extendible_hash.c
alignment = *(char *) args;  offset += sizeof (alignment);
depth     = *((char *) args + offset);  /* ... is_temp read next ... */
pgbuf_set_page_ptype (thread_p, page_p, PAGE_EHASH);                     /* (1) stamp ptype */
spage_initialize (thread_p, page_p, UNANCHORED_KEEP_SEQUENCE, alignment, DONT_SAFEGUARD_RVSPACE); /* (2) */
bucket_header.local_depth = depth;                                       /* (3) header = depth 0 */
// ... bucket_recdes = &bucket_header, REC_HOME, sizeof (EHASH_BUCKET_HEADER) ...
success = spage_insert (thread_p, page_p, &bucket_recdes, &slot_id);     /* (4) header -> slot 0 */
if (success != SP_SUCCESS)
  {
    if (success != SP_ERROR)            /* should-never-happen: tiny record refused on empty page */
      { er_set (ER_FATAL_ERROR_SEVERITY, ...); error_code = ER_FAILED; }
    else { ASSERT_ERROR_AND_SET (error_code); }  /* real error already set */
    return error_code;                  /* <- page left fixed, undone by file_alloc */
  }
if (!is_temp)
  log_append_undoredo_data2 (thread_p, RVEH_INIT_BUCKET, NULL, page_p, -1, 0, 2, NULL, args);  /* (5) */
pgbuf_set_dirty (thread_p, page_p, DONT_FREE);
return NO_ERROR;

All three spage_insert outcomes are annotated inline; is_temp true skips logging. RVEH_INIT_BUCKET via log_append_undoredo_data2 is undoredo, its 2-byte {alignment, depth} payload serving both directions; the redo handler ehash_rv_init_bucket_redo re-runs spage_initialize + spage_insert, mirroring this function (returning er_errid () rather than ER_FAILED).

INVARIANT — slot 0 holds the bucket header. Every bucket page keeps its EHASH_BUCKET_HEADER (a single char local_depth) at slot 0, inserted before any data record; UNANCHORED_KEEP_SEQUENCE preserves slot order. Enforcement: the header spage_insert runs on the empty page before any entry can be added. If violated, every depth read in split/merge (Ch 6, 8) reads garbage.

2.9 Directory file, header, and the single entry

The directory file is created second, pinned to the bucket’s volume, then page 0 written by hand. The header overlaid on the page is EHASH_DIR_HEADER, whose fields are declared “ordered according to their sizes”:

// struct ehash_dir_header -- src/storage/extendible_hash.c
struct ehash_dir_header
{
  VFID bucket_file;             /* bucket file identifier */
  VFID overflow_file;           /* overflow (buckets) file identifier */
  int local_depth_count[EHASH_HASH_KEY_BITS + 1];  /* histogram: count of buckets per local depth */
  DB_TYPE key_type;             /* type of the keys */
  short depth;                  /* global depth of the directory */
  char alignment;               /* alignment value used on slots of bucket pages */
};

Field	Role	Why it exists
bucket_file	VFID of the bucket file	Sole link directory -> buckets; the bucket VFID is in no EHID, so it must persist here
overflow_file	VFID of the long-string overflow file, NULL until first long key	Keeps oversized string keys off bucket pages
local_depth_count[]	Per-local-depth bucket-count histogram, EHASH_HASH_KEY_BITS + 1 entries	Ch 9 reads it to detect the shrink condition without scanning entries
key_type	DB_TYPE of the keys (STRING or OBJECT)	Lets lookup/insert hash and compare keys without a side channel
depth	Global depth — directory-index bits in use	Sets directory size (2^depth) and the split decision (Ch 7)
alignment	Slot alignment carried over from 2.6	All buckets share one alignment when formatted

Each directory slot is a one-field EHASH_DIR_RECORD:

// struct ehash_dir_record -- src/storage/extendible_hash.c
struct ehash_dir_record
{
  VPID bucket_vpid;             /* bucket pointer */
};

Field	Role	Why it exists
bucket_vpid	VPID of the bucket this directory slot points at	The directory is an array of these pointers; multiple slots may alias one bucket when local_depth < depth

// ehash_create_helper -- src/storage/extendible_hash.c
if (exp_num_entries < 0) exp_dir_pages = 1;       /* one-page collapse */
else { ehash_dir_locate (&exp_dir_pages, &exp_bucket_pages); exp_dir_pages++; }  /* INDEX -> count */
dir_vfid.volid = bucket_vfid.volid;
if (file_create_ehash_dir (...) != NO_ERROR) { ASSERT_ERROR (); goto exit_on_error; } /* Branch P-no */
if (file_alloc (thread_p, &dir_vfid, is_tmp ? file_init_temp_page_type : file_init_page_type,
                &ptype, &dir_vpid, &dir_page_p) != NO_ERROR)   /* generic init, NOT a hash callback */
  { ASSERT_ERROR (); goto exit_on_error; }        /* Branch Q-no */
if (dir_page_p == NULL) { assert_release (false); goto exit_on_error; } /* Branch R-yes: defensive */
#if !defined (NDEBUG)
  pgbuf_check_page_ptype (thread_p, dir_page_p, PAGE_EHASH);   /* dir-create re-checks ptype */
#endif
dir_header_p = (EHASH_DIR_HEADER *) dir_page_p;
dir_header_p->depth = 0;                          /* <- global depth 0 */
// ... key_type, alignment, bucket_file=bucket_vfid, overflow_file=NULL set here ...
dir_header_p->local_depth_count[0] = 1;           /* <- one bucket at local depth 0 */
// ... zero remaining local_depth_count[1..EHASH_HASH_KEY_BITS] ...
dir_record_p = (EHASH_DIR_RECORD *) ((char *) dir_page_p + EHASH_DIR_HEADER_SIZE);
dir_record_p->bucket_vpid = bucket_vpid;          /* <- entry[0] -> bucket page 0 */

A trailing loop zeroes histogram indices 1..EHASH_HASH_KEY_BITS (index 0 is the only nonzero entry). Page 0 uses the generic file_init_page_type (no hashing callback) since the contents are overwritten by hand at once and a crash drops the file anyway, yet PAGE_EHASH is still re-checked in debug. EHASH_DIR_HEADER_SIZE rounds the header up to an int boundary, so the first EHASH_DIR_RECORD sits right after it.

STARTING INVARIANT — depth 0, one entry, one bucket at local depth 0. A fresh table has dir_header.depth == 0, one EHASH_DIR_RECORD pointing at bucket page 0, and local_depth == 0 with local_depth_count[0] == 1 — the base case every later algorithm assumes (Ch 6 only raises local depth; Ch 7 doubles only when it would exceed depth). Enforcement: these three writes happen unconditionally before the page is dirtied and the EHID returned. If violated (e.g. local_depth_count[0] left 0), the first split’s shrink-check and fan-out arithmetic start from a wrong baseline.

RVEH_INIT_DIR — redo-only

// ehash_create_helper -- src/storage/extendible_hash.c
if (!is_tmp)
  log_append_redo_data2 (thread_p, RVEH_INIT_DIR, &dir_vfid, dir_page_p, 0,
                         EHASH_DIR_HEADER_SIZE + sizeof (EHASH_DIR_RECORD), dir_page_p);

This is log_append_redo_data2 — redo only, no undo (source: “Don’t need UNDO since we are just creating the file. If we abort, the file is removed.”). On rollback exit_on_error destroys the directory file, so only forward recovery needs the image; the handler ehash_rv_init_dir_redo stamps PAGE_EHASH then log_rv_copy_char-copies the logged image, restoring the seed state exactly.

2.10 Success tail and the page-fix wrappers

On success the helper dirties+frees dir_page_p, copies dir_vfid and dir_vpid.pageid into the EHID (the overwrite of 2.7), and return ehid_p; the bucket file is reachable only through dir_header.bucket_file. exit_on_error (Branch ERR) destroys whichever VFIDs are non-null: permanent via file_postpone_destroy, temporary via file_destroy. The three page-fix wrappers later chapters use bottom out in ehash_fix_old_page:

// ehash_fix_old_page -- src/storage/extendible_hash.c
page_p = pgbuf_fix (thread_p, vpid_p, OLD_PAGE, latch_mode, PGBUF_UNCONDITIONAL_LATCH);
if (page_p == NULL)
  {
    if (er_errid () == ER_PB_BAD_PAGEID)         /* <- only this errid gets re-mapped */
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_UNKNOWN_EXT_HASH, 4, /* ...vfid/vpid... */);
    return NULL;                                 /* any other failure returned as-is */
  }
#if !defined (NDEBUG)
  (void) pgbuf_check_page_ptype (thread_p, page_p, PAGE_EHASH);   /* <- ptype guard */
#endif
  return page_p;

vfid is only for error reporting here. The other two delegate to it: ehash_fix_ehid_page fixes the directory root via {ehid->vfid.volid, ehid->pageid} (the EHID-to-header path); ehash_fix_nth_page fixes the offset-th page via file_numerable_find_nth (ASSERT_ERROR ()/NULL on failure) — the ordinal walk over a multi-page directory.

INVARIANT — every hash page carries PAGE_EHASH ptype. Bucket pages get it from ehash_initialize_bucket_new_page, directory pages from the file_init_page_type arg, re-stamped by the redo handler. Enforcement: ehash_fix_old_page calls pgbuf_check_page_ptype on every fix in debug builds. If violated (a page reused without the stamp), pgbuf_check_page_ptype trips at fix time rather than parsing a non-hash page as a bucket.

2.11 Chapter summary — key takeaways

1. A hash table is two numerable files (bucket + directory) tagged with the same FILE_EHASH_DES { class_oid, attr_id } — metadata the algorithm never reads.
2. Only DB_TYPE_STRING and DB_TYPE_OBJECT are reachable; fixed-width cases compile out under ENABLE_UNUSED_FUNCTION, and DB_TYPE_STRING’s 1 is a sentinel (real string budget is computed in 2.5).
3. exp_num_entries < 0 collapses both page estimates to one; else 20 + sizeof(OID) + 4 (strings) or key_size + sizeof(OID) + 4 (OIDs) over CEIL_PTVDIV — a locality hint only.
4. Volid flows caller -> bucket -> directory; the EHID is overwritten with the directory VFID + root pageid only at the end.
5. Bucket page 0 is formatted by the file_alloc callback ehash_initialize_bucket_new_page: PAGE_EHASH, spage_initialize, the one-byte EHASH_BUCKET_HEADER (local_depth = 0) at slot 0, RVEH_INIT_BUCKET undoredo (permanent only).
6. The directory root is written by hand into an EHASH_DIR_HEADER — depth = 0, local_depth_count[0] = 1, one EHASH_DIR_RECORD; its RVEH_INIT_DIR log is redo-only since an aborted create destroys the file.
7. Starting invariant: depth=0, one entry, one bucket at local depth 0; every hash page carries the PAGE_EHASH ptype ehash_fix_old_page re-checks.

Chapter 3: Hashing and Directory Addressing

Every CRUD operation starts the same way: a user key becomes a fixed-width pseudo-key, its leading bits select a directory slot, and the slot’s VPID names one bucket page. This chapter dissects that shared addressing skeleton in isolation, before search (Ch 4), insert (Ch 5), and delete (Ch 8) add their own logic. For the conceptual framing (global vs. local depth, doubling), see the companion’s “Extendible hashing in one picture” and “Depth”.

Three steps: hash (ehash_hash → 32-bit EHASH_HASH_KEY), locate index (FIND_OFFSET takes the top depth bits), resolve to VPID (ehash_find_bucket_vpid maps the index through ehash_dir_locate, fixes the directory page, reads the VPID). ehash_find_bucket_vpid_with_hash chains all three — the single entry point every CRUD path calls.

3.1 The pseudo-key type and its width

The pseudo-key is a 32-bit unsigned integer, the output of hashing, not a record struct:

// EHASH_HASH_KEY -- src/storage/extendible_hash.c
typedef unsigned int EHASH_HASH_KEY;  /* Pseudo_key type */
#define EHASH_HASH_KEY_BITS  (sizeof(EHASH_HASH_KEY) * 8)   /* = 32 */

EHASH_HASH_KEY is a fieldless typedef. FIND_OFFSET reads the directory index from the numerically high-order bits of the word — it right-shifts the unsigned integer value, not a byte array, so “leading bits” means most-significant value bits regardless of host byte order. The hash functions therefore aim their most-variable output at the high-order bits and park a checksum at the low end:

Value zone (numeric MSB→LSB)	Role	Why it exists
high-order bits (read first by FIND_OFFSET)	Primary index bits	Most-variable output lives where the directory indexes
middle bits	Secondary/tertiary index bits	A deeper directory walks further down the word
low-order bits	Checksum (string: signed byte-sum added to the word; OID: byte-XOR written into the lowest-addressed byte)	Cheap mixing; reached only as depth nears 32

This is a tendency, not a bit-exact layout: the string path adds a signed sum to the whole word (it can carry up and be negative), and the OID path overwrites the lowest-addressed byte — the numeric LSB only on little-endian hosts. The “checksum in the low byte” picture is endianness- and carry-dependent; do not treat it as a rigid struct.

INVARIANT — global depth never exceeds the pseudo-key width. FIND_OFFSET extracts depth bits from a 32-bit word, so dir_header->depth is bounded by EHASH_HASH_KEY_BITS (32); the shrink bookkeeping reserves EHASH_HASH_KEY_BITS + 1 counter slots (local_depth_count[33]), so depth 0..32 is indexable. If violated (depth 33+), GETBITS shifts by a negative amount — undefined behaviour in C, silently corrupting the index.

FIND_OFFSET aliases GETBITS, taking the first depth bits, left-adjusted (pos=1):

// FIND_OFFSET / GETBITS -- src/storage/extendible_hash.c
#define GETBITS(value, pos, n) \
  ( ((value) >> ( EHASH_HASH_KEY_BITS - (pos) - (n) + 1)) & (~(~0UL << (n))) )
#define FIND_OFFSET(hash_key, depth) (GETBITS((hash_key), 1, (depth)))
/*  pos=1, n=depth: shift the value right by (32 - depth), mask to depth bits */

INVARIANT — exactly the top depth bits select the slot. With pos=1, n=depth, GETBITS shifts right by 32 - depth and masks depth low bits, so the result is precisely the depth most-significant bits of the value — no more, no fewer. This is what makes a directory doubling (depth d → d+1) split each old slot i into siblings 2i and 2i+1: appending one bit of resolution.

3.2 ehash_hash — type dispatch

ehash_hash is a switch on DB_TYPE; only two arms compile into a normal build:

// ehash_hash -- src/storage/extendible_hash.c
  switch (key_type)
    {
    case DB_TYPE_STRING:
      hash_key = ehash_hash_string_type (key, (char *) original_key_p); break;
    case DB_TYPE_OBJECT:
      hash_key = ehash_hash_eight_bytes_type (key); break;   /* OIDs */
#if defined (ENABLE_UNUSED_FUNCTION)
    /* ... BIGINT/DOUBLE/MONETARY -> eight_bytes; FLOAT/DATE/.../INTEGER -> four_bytes; SHORT -> two_bytes ... */
#endif
    default:
      er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);  /* <- hash_key stays 0 */
    }
  return hash_key;

Branches. DB_TYPE_STRING → ehash_hash_string_type; DB_TYPE_OBJECT → ehash_hash_eight_bytes_type. The wide-numeric arms sit behind #if defined (ENABLE_UNUSED_FUNCTION), absent from a normal build. The default arm raises fatal ER_EH_CORRUPTED and returns hash_key = 0 (its initial value), mapping every unsupported key to entry 0. CUBRID hashes only class-name strings and OIDs, so these two arms are the whole story.

3.3 ehash_hash_string_type — fold, then triple-pass pack

Two stages: a fold into a 4-byte intermediate, and a triple-pass pack spreading it across the high three bytes plus a byte-sum. Stage 1 holds the only early-return:

// ehash_hash_string_type (stage 1) -- src/storage/extendible_hash.c
  length = (int) strlen (key_p);
  if (length > 0)                               /* <- empty/all-space string skips folding */
    {
      if (char_isspace (*(char *) (key_p + length - 1)))      /* trailing space present */
        {
          for (p = key_p + length - 1; char_isspace (*p) && (p > key_p); p--) ;  /* scan back, stop at first char */
          length = (int) (p - key_p + 1);
          key_p = new_key_p = (char *) malloc (length + 1);
          if (key_p == NULL)
            return 0;                           /* <- OOM: bail with all-zeros pseudo-key */
          memcpy (key_p, original_key_p, length); *(char *) (key_p + length) = '\0';
        }
      // ... condensed: fold whole 4-byte words into hash_key (+=), then the
      //   leftover bytes, each shift-aligned by its position i ...
      if (new_key_p) free_and_init (new_key_p);
    }

Stage-1 branches. length > 0 false — empty/all-space string skips both fold loops; hash_key stays 0 into stage 2. Not an error: stage 2 still runs mht_1/2/3strhash over the zeroed intermediate, yielding a deterministic non-zero pseudo-key. Trailing space present — scan back (the (p > key_p) guard stops at the first char so an all-space tail collapses to length 1), recompute length, malloc a copy from original_key_p; on NULL, return 0 (entry 0), the only place string hashing can fail and a distinct exit from the normal return hash_key + Char. No trailing space — fold runs on key_p in place, nothing freed.

Stage 2 re-hashes the folded word:

// ehash_hash_string_type (stage 2) -- src/storage/extendible_hash.c
  memcpy (&copy_psekey, &hash_key, sizeof (EHASH_HASH_KEY));
  copy_psekey[sizeof (EHASH_HASH_KEY)] = '\0';
  hash_key = 0;
  byte = mht_1strhash (copy_psekey, 509); hash_key += (byte << (8 * (sizeof (EHASH_HASH_KEY) - 1)));  /* up 24 */
  byte = mht_2strhash (copy_psekey, 509); hash_key += (byte << (8 * (sizeof (EHASH_HASH_KEY) - 2)));  /* up 16 */
  byte = mht_3strhash (copy_psekey, 509); hash_key += (byte << (8 * (sizeof (EHASH_HASH_KEY) - 3)));  /* up 8 */
  Char = '\0';                                  /* signed char accumulator */
  for (i = 0; i < sizeof (EHASH_HASH_KEY); i++) Char += (char) copy_psekey[i];  /* byte-sum */
  return hash_key + Char;                       /* normal path: add signed sum to the whole word */

mht_1strhash/mht_2strhash/mht_3strhash are three independent string hashes in src/base/memory_hash.c, each reduced mod 509. Mod 509 spans 0..508 — 9 bits, not 8 — so each result, shifted then added, makes the three high “bytes” not strictly disjoint: an output above 255 carries into the next byte (extra mixing, not a clean split). Char is a signed char summed across the four intermediate bytes and added to the whole 32-bit word by return hash_key + Char — it can carry beyond the low byte and can be negative, so it is a low-end perturbation, not a clean low-byte write (contrast the OID path in §3.4, which overwrites a byte in place).

Why the triple-pass into the high bytes? CUBRID class names share long common prefixes (_db_class, _db_attribute, owner-qualified names). A single fold puts that most-correlated information at the top — the bits FIND_OFFSET reads first — so prefix-sharing keys collide into one bucket; three algorithms over the folded intermediate decorrelate those leading bits.

3.4 ehash_hash_eight_bytes_type — OID folding via htonl

OIDs fold two 32-bit words with htonl, then XOR a checksum into the lowest-addressed byte:

// ehash_hash_eight_bytes_type -- src/storage/extendible_hash.c
  for (i = 0; i < sizeof (double) / sizeof (int); i++)   /* two iterations */
    { memcpy (&Int, key_p, sizeof (int)); hash_key += htonl (Int); key_p += sizeof (int); }
  Char = '\0';
  key_p = (char *) &hash_key;
  for (i = 0; i < sizeof (EHASH_HASH_KEY); i++) Char ^= (char) *key_p++;   /* XOR, not sum */
  memcpy (&hash_key, &Char, sizeof (char));      /* overwrite lowest-addressed byte */
  return hash_key;

Two differences from the string path. htonl forces canonical big-endian byte order before folding, so the same logical OID hashes identically on any host — pseudo-keys decide bucket placement and must reproduce on recovery. And the checksum is an XOR written into the lowest-addressed byte in place via memcpy, where the string path adds a signed sum to the whole word. Unlike the htonl fold, this final overwrite is not byte-order normalized — the lowest memory byte is the numeric LSB on little-endian, the MSB on big-endian — but it is consistent on a single host, which is all the directory needs. No early returns.

3.5 ehash_dir_locate — index to (page_no, offset)

The directory is one flat EHASH_DIR_RECORD array split across pages; the root page also holds the EHASH_DIR_HEADER, so it has fewer slots (EHASH_NUM_FIRST_PAGES) than later pages (EHASH_NUM_NON_FIRST_PAGES). ehash_dir_locate maps a flat index to (page_no, byte offset):

// ehash_dir_locate -- src/storage/extendible_hash.c
  offset = *out_offset_p;                       /* in: the flat entry index */
  if (offset < EHASH_NUM_FIRST_PAGES)
    { offset = offset * sizeof (EHASH_DIR_RECORD) + EHASH_DIR_HEADER_SIZE;  /* skip header */
      page_no = 0; }                            /* root page */
  else
    { offset -= EHASH_NUM_FIRST_PAGES;          /* relative to page 1 */
      page_no = offset / EHASH_NUM_NON_FIRST_PAGES + 1;
      offset = (offset % EHASH_NUM_NON_FIRST_PAGES) * sizeof (EHASH_DIR_RECORD); }
  *out_page_no_p = page_no;
  *out_offset_p = offset;                       /* out: byte offset within page */

EHASH_NUM_FIRST_PAGES is (DB_PAGESIZE - EHASH_DIR_HEADER_SIZE) / sizeof(EHASH_DIR_RECORD); EHASH_NUM_NON_FIRST_PAGES is DB_PAGESIZE / sizeof(EHASH_DIR_RECORD). Branches. Index < EHASH_NUM_FIRST_PAGES → root page (byte offset = index × record size + EHASH_DIR_HEADER_SIZE, page_no = 0). Otherwise → later page: subtract the root capacity, then a single division and modulo give page_no = quotient + 1 and offset = remainder × record size (no header skip — non-first pages are pure entry arrays). API quirk: the same out_offset_p carries the index in and the byte offset out; the comment block notes the macro-style / + % is constant-time versus successive subtraction.

3.6 ehash_find_bucket_vpid — resolve index to a bucket VPID

Given an index (location), read the stored VPID: call ehash_dir_locate, then branch on root vs. later page:

// ehash_find_bucket_vpid -- src/storage/extendible_hash.c
  ehash_dir_locate (&dir_offset, &location);    /* dir_offset<-page_no, location<-byte offset */
  if (dir_offset != 0)                          /* <- non-root directory page */
    {
      dir_page_p = ehash_fix_nth_page (thread_p, &ehid_p->vfid, dir_offset, latch);
      if (dir_page_p == NULL)
        return ER_FAILED;                       /* <- fix failed */
      dir_record_p = (EHASH_DIR_RECORD *) ((char *) dir_page_p + location);
      pgbuf_unfix_and_init (thread_p, dir_page_p);   /* read VPID below, then release */
    }
  else                                          /* <- root page, already pinned by caller */
    dir_record_p = (EHASH_DIR_RECORD *) ((char *) dir_header_p + location);
  *out_vpid_p = dir_record_p->bucket_vpid;
  return NO_ERROR;

Note the argument-order swap: ehash_dir_locate (&dir_offset, &location) writes the page number into dir_offset (its out_page_no_p) and the byte offset into location (its in/out out_offset_p). Branches. dir_offset is the page number. != 0: entry on directory page 1, 2, …; ehash_fix_nth_page resolves the n-th numerable page via file_numerable_find_nth and fixes it. NULL → ER_FAILED (caller unfixes the root); else copy bucket_vpid (a value copy out of the page) and unfix immediately. == 0: entry on the root page, held by the caller as dir_header_p; no latch consumed.

INVARIANT — the latch parameter applies only to non-root directory pages. The root is fixed once by ehash_find_bucket_vpid_with_hash under root_latch; this function never re-fixes it, spending latch only in the dir_offset != 0 branch and releasing (pgbuf_unfix_and_init) before return. If violated (the root branch re-fixing the same page), a thread would re-latch a page it already holds.

3.7 The NULL_PAGEID directory hole

ehash_find_bucket_vpid always succeeds in reading a VPID, but the value may be { NULL_PAGEID, … } — a directory hole: a slot that, after a doubling (Ch 7) or merge (Ch 8), points at no live bucket. The layer returns NO_ERROR and lets the caller decide:

// ehash_search (caller) -- src/storage/extendible_hash.c
  if (bucket_vpid.pageid == NULL_PAGEID)
    { result = EH_KEY_NOTFOUND; goto end; }     /* <- a hole means the key cannot exist here */

Search and delete read a hole as “key absent” (EH_KEY_NOTFOUND); insert reads it as “create and connect a bucket first.” It is a normal addressing result, not a failure — ER_FAILED is reserved for a page-fix failure.

3.8 ehash_find_bucket_vpid_with_hash — the wrapper all CRUD paths call

Fix the root, hash, compute the index, resolve to a VPID — optionally returning the hash key (insert needs it for splits) and index (merge needs it):

// ehash_find_bucket_vpid_with_hash -- src/storage/extendible_hash.c
  dir_root_page_p = ehash_fix_ehid_page (thread_p, ehid_p, root_latch);
  if (dir_root_page_p == NULL)
    return NULL;                                   /* <- root fix failed */
  dir_header_p = (EHASH_DIR_HEADER *) dir_root_page_p;
  hash_key = ehash_hash (key_p, dir_header_p->key_type);   /* type from header */
  if (out_hash_key_p) *out_hash_key_p = hash_key;          /* optional out */
  location = FIND_OFFSET (hash_key, dir_header_p->depth);   /* top `depth` bits */
  if (out_location_p) *out_location_p = location;          /* optional out */
  if (ehash_find_bucket_vpid (thread_p, ehid_p, dir_header_p, location, bucket_latch, out_vpid_p) != NO_ERROR)
    {
      pgbuf_unfix_and_init (thread_p, dir_root_page_p);     /* <- release root on failure */
      return NULL;
    }
  return dir_root_page_p;                          /* <- success: caller still holds root */

Branches. Root fix fails (== NULL): return NULL, nothing held. out_hash_key_p/out_location_p non-NULL: each is stored; NULL skips it. ehash_find_bucket_vpid fails: unfix the root, return NULL — the wrapper owns the root’s lifetime on the error path. Success: return the still-fixed root page; the caller gets it pinned under root_latch, the VPID in out_vpid_p, optionally hash key/location, and must unfix the root when done.

root_latch governs the root, bucket_latch any non-root directory page (ehash_search reads both with PGBUF_LATCH_READ; insert/delete use write latches). Key type comes from dir_header_p->key_type (Ch 2).

stateDiagram-v2
  [*] --> FixRoot
  FixRoot --> ReturnNull1: root fix failed
  FixRoot --> Hash: root pinned under root_latch
  Hash --> FindOffset: hash_key computed, optional out stored
  FindOffset --> ResolveVpid: location = top depth bits
  ResolveVpid --> ReturnNull2: ehash_find_bucket_vpid ER_FAILED \n unfix root
  ResolveVpid --> Success: NO_ERROR, out_vpid filled
  Success --> [*]: return pinned root page
  ReturnNull1 --> [*]
  ReturnNull2 --> [*]

Figure 3-1 — ehash_find_bucket_vpid_with_hash, end to end.

3.9 Chapter summary — key takeaways

1. The addressing skeleton is hash → FIND_OFFSET → resolve VPID, wrapped by ehash_find_bucket_vpid_with_hash — the single entry every CRUD path uses.
2. ehash_hash has two live arms: DB_TYPE_STRING → ehash_hash_string_type, DB_TYPE_OBJECT → ehash_hash_eight_bytes_type; default raises ER_EH_CORRUPTED and returns 0.
3. FIND_OFFSET reads the numerically high-order depth bits of the 32-bit EHASH_HASH_KEY (a value right-shift, byte-order independent); the hash functions aim their most-variable output there and put a checksum at the low end — string-side as a signed sum added to the whole word, OID-side as an XOR overwriting the lowest-addressed byte, the latter being the numeric LSB only on little-endian hosts.
4. String hashing runs three mod-509 algorithms into the high bytes to decorrelate shared class-name prefixes; the only failure exit is the trailing-space malloc returning NULL (return 0).
5. OID hashing uses htonl for an endian-independent, recovery-reproducible fold, then XORs a checksum into the lowest-addressed byte in place, with no early returns.
6. ehash_dir_locate/ehash_find_bucket_vpid split on root vs. later page: the root is pre-pinned by the caller (no fix, no latch); later pages are fixed via ehash_fix_nth_page, read, released — latch is spent only on the non-root branch.
7. A NULL_PAGEID VPID is a directory hole, returned as NO_ERROR — a normal “key not here”, distinct from the ER_FAILED reserved for page-fix failures.

Chapter 4: Searching Inside a Bucket

Chapter 3 ended the moment the directory translated a hashed key into a single bucket_vpid. This chapter answers: given the bucket page, how is the user key found and its OID handed back? The read path is the cheapest extendible-hash operation — it never modifies a page and holds only shared latches — but its in-bucket layout and two-latch protocol are subtle enough that anyone about to touch ehash_insert or ehash_delete must see every branch. We trace ehash_search, then its helpers ehash_locate_slot, ehash_binary_search_bucket, ehash_compare_key, ehash_read_oid_from_record. For the walk producing bucket_vpid see Chapter 3, for UNANCHORED_KEEP_SEQUENCE mechanics Chapter 2, and for the theory the high-level companion (cubrid-extendible-hash.md, “Bucket structure and local depth”).

4.1 The in-bucket record layout

Every helper depends on the layout a bucket page is initialized with:

// ehash_initialize_bucket_new_page -- src/storage/extendible_hash.c
spage_initialize (thread_p, page_p, UNANCHORED_KEEP_SEQUENCE, alignment, DONT_SAFEGUARD_RVSPACE);

UNANCHORED_KEEP_SEQUENCE is the load-bearing choice: it keeps the slot array ordered by record content, so slots stay in ascending user-key order even when a record is spliced into the middle — the sole reason a binary search is legal here.

Each data record (slot 1..N; slot 0 is the EHASH_BUCKET_HEADER) is OID-first, key-second — recdes.data holds sizeof(OID) bytes (pageid|volid|slotid), then the variable-length user key. This is the reverse of a B+Tree leaf. The fixed-width OID at offset 0 lets the value-reader copy a fixed stride and the comparator skip it with one += sizeof(OID), never measuring the key.

Figure 4-1. One bucket data record; value-reader and comparator land on opposite halves.

4.2 ehash_search end to end

ehash_search, the only public entry point, sets its default, fires guard 1 before any latch, then the Chapter 3 walk fixes the root and fills bucket_vpid:

// ehash_search -- src/storage/extendible_hash.c
EH_SEARCH result = EH_KEY_NOTFOUND;   /* <- pessimistic default */
if (ehid_p == NULL || key_p == NULL)
  return EH_KEY_NOTFOUND;             /* <- guard 1: bad args, no page fixed, plain return */
dir_root_page_p =
  ehash_find_bucket_vpid_with_hash (thread_p, ehid_p, key_p, PGBUF_LATCH_READ, PGBUF_LATCH_READ, &bucket_vpid,
                                    NULL, NULL);          /* <- root + bucket-lookup both READ */
if (dir_root_page_p == NULL)
  return EH_ERROR_OCCURRED;            /* <- guard 2: directory fault; root never returned */
dir_header_p = (EHASH_DIR_HEADER *) dir_root_page_p;     /* <- key_type lives in the header */

Guard 1 — null ehid/key. A direct return because nothing is fixed; garbage yields a deliberate “no such key”, not an error.

Guard 2 — directory fault. Helper returns NULL; we return EH_ERROR_OCCURRED directly because no page is held (the helper cleans up its partial state). The PGBUF_LATCH_READ, PGBUF_LATCH_READ pair makes this a pure reader; the bucket is not fixed here, only its VPID resolved. After this the root is held, so the three remaining exits run end::

// ehash_search -- src/storage/extendible_hash.c
if (bucket_vpid.pageid == NULL_PAGEID)     /* <- guard 3: directory hole */
  { result = EH_KEY_NOTFOUND; goto end; }

bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid, &bucket_vpid, PGBUF_LATCH_READ);
if (bucket_page_p == NULL)                 /* <- guard 4: bucket fix failed */
  { result = EH_ERROR_OCCURRED; goto end; }

if (ehash_locate_slot (thread_p, bucket_page_p, dir_header_p->key_type, key_p, &slot_id) == false)
  { result = EH_KEY_NOTFOUND; goto end; }  /* <- guard 5: key absent */
(void) spage_get_record (thread_p, bucket_page_p, slot_id, &recdes, PEEK);   /* <- PEEK: no copy */
(void) ehash_read_oid_from_record (recdes.data, value_p);                    /* <- extract OID */
result = EH_KEY_FOUND;

Guard 3 — directory hole (NULL_PAGEID). A pointer may legitimately name “no bucket yet”; the prefix maps to an empty region, so the key cannot exist. We jump to cleanup without fixing a second page — why a search can cost one fix. Guard 4 — bucket fix failed. Non-null bucket_vpid but the page cannot be fixed (I/O error, deallocated): EH_ERROR_OCCURRED.

Guard 5 — key absent. ehash_locate_slot returns false; slot_id is then the would-be insert position (unused by a reader, used by Chapter 5).

Hit path. On true, slot_id names the slot. spage_get_record with PEEK returns a recdes pointing into the page buffer — no copy, valid only under the latch — so the OID is copied into value_p before any unfix, and result is EH_KEY_FOUND.

Invariant — every post-Guard-2 path drains through end:. Once the root is fixed the only exit is end: (goto end for guards 3 and 5, fall-through on the hit); a direct return would leak that page. Guards 1 and 2 are the only direct returns — correct because no page is held.

// ehash_search -- src/storage/extendible_hash.c
end:
  if (bucket_page_p)
    pgbuf_unfix_and_init (thread_p, bucket_page_p);   /* <- bucket released first */
  if (dir_root_page_p)
    pgbuf_unfix_and_init (thread_p, dir_root_page_p); /* <- then root */
  return result;

Latch-release order: bucket first, then root. Each if (ptr) makes the label reachable from any state (root-only on guards 3/5, both on the hit); pgbuf_unfix_and_init unfixes and nulls the pointer, so a never-taken page is a no-op. Releasing the leaf first mirrors the acquisition.

flowchart TD
  A["ehash_search"] --> B{"ehid or key NULL?"}
  B -->|yes| R1["guard 1: return NOTFOUND<br/>(no page held)"]
  B -->|no| C["find_bucket_vpid_with_hash<br/>root+bucket READ"]
  C --> D{"root NULL?"}
  D -->|yes| R2["guard 2: return ERROR<br/>(no page held)"]
  D -->|no| E{"bucket_vpid == NULL_PAGEID?"}
  E -->|yes| F1["guard 3: NOTFOUND; goto end"]
  E -->|no| G["ehash_fix_old_page READ"]
  G --> H{"bucket NULL?"}
  H -->|yes| F2["guard 4: ERROR; goto end"]
  H -->|no| I{"locate_slot == false?"}
  I -->|yes| F3["guard 5: NOTFOUND; goto end"]
  I -->|no| J["get_record PEEK; read_oid<br/>result=FOUND"]
  F1 --> K["end:"]
  F2 --> K
  F3 --> K
  J --> K
  K --> L["unfix bucket if held"] --> M["unfix root if held"] --> N["return result"]

Figure 4-2. ehash_search — all five guard branches and the shared cleanup.

4.3 ehash_locate_slot — the empty-bucket edge

Handles the empty-bucket edge before delegating:

// ehash_locate_slot -- src/storage/extendible_hash.c
num_record = spage_number_of_records (bucket_page_p) - 1;   /* <- minus the header slot */
if (num_record < 1)                                         /* <- bucket has only the header */
  {
    if (spage_next_record (bucket_page_p, &first_slot_id, &recdes, PEEK) != S_SUCCESS)
      { er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
        *out_position_p = 1; return false; }                /* <- corruption: header missing */
    *out_position_p = first_slot_id + 1;                    /* <- insert just after header */
    return false;
  }
return ehash_binary_search_bucket (thread_p, bucket_page_p, num_record, key_type, key_p, out_position_p);

Two branches. num_record < 1 (empty): return false; to hand the insert path a slot it walks via spage_next_record from first_slot_id = -1 (returns the header) and sets *out_position_p = first_slot_id + 1, one past it. The nested branch fires only if even the header is unreadable — fatal ER_EH_CORRUPTED. An empty bucket never reaches the search. num_record >= 1: delegates through.

Invariant — the binary search is entered only with num_record >= 1. Its do { } while body runs before the bound is tested, so num_record == 0 would not be saved by high < low; ehash_locate_slot guarantees this, handling the empty case outside the loop.

4.4 ehash_binary_search_bucket — the O(log m) search

Binary search over 1..num_record:

// ehash_binary_search_bucket -- src/storage/extendible_hash.c
low = 1;
high = num_record;
do
  {
    middle = (high + low) >> 1;                              /* <- midpoint slot */
    if (spage_get_record (thread_p, bucket_page_p, middle, &recdes, PEEK) != S_SUCCESS)
      { er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
        return false; }                                      /* <- unreadable slot => corrupt */
    bucket_record_p = (char *) recdes.data;
    bucket_record_p += sizeof (OID);                         /* <- skip OID, point at key bytes */
    if (ehash_compare_key (thread_p, bucket_record_p, key_type, key_p, recdes.type, &compare_result) != NO_ERROR)
      return false;                                          /* <- comparator error path */
    if (compare_result == 0)
      { *out_position_p = middle; return true; }             /* <- HIT */
    if (compare_result < 0)
      high = middle - 1;                                     /* <- key < record: go left */
    else
      low = middle + 1;                                      /* <- key > record: go right */
  }
while (high >= low);

The += sizeof(OID) is the §4.1 layout dependency; compare_result is key - record (negative = key sorts first). Three loop exits: corrupt slot (→ ER_EH_CORRUPTED, false, position untouched), comparator error (unknown type, §4.5 → false, position unset), and hit (== 0 → middle, true).

On fall-through (high < low, key absent) the tail computes the insertion position: if (high < middle) *out_position_p = middle; else *out_position_p = middle + 1; return false; — if high dropped below the last-probed middle the key belongs at middle, else at middle + 1. A reader ignores it; the Chapter 5 insert path uses it to splice the record preserving UNANCHORED_KEEP_SEQUENCE order.

flowchart TD
  A["low=1, high=num_record"] --> B["middle=(high+low)>>1"]
  B --> C{"get_record ok?"}
  C -->|no| X1["ER_EH_CORRUPTED; false"]
  C -->|yes| E{"compare_key ok?"}
  E -->|no| X2["false: bad key type"]
  E -->|yes| F{"compare_result"}
  F -->|== 0| H["*pos=middle; true HIT"]
  F -->|< 0| G1["high=middle-1"]
  F -->|> 0| G2["low=middle+1"]
  G1 --> I{"high >= low?"}
  G2 --> I
  I -->|yes| B
  I -->|no| J{"high < middle?"}
  J -->|yes| K1["*pos=middle"] --> L["false: MISS, insert pos set"]
  J -->|no| K2["*pos=middle+1"] --> L

Figure 4-3. ehash_binary_search_bucket — both fatal paths, the hit, and the two miss positions.

4.5 ehash_compare_key — type-dispatched three-way compare

Dispatches on key_type; two cases are live, the rest fenced behind ENABLE_UNUSED_FUNCTION:

// ehash_compare_key -- src/storage/extendible_hash.c
switch (key_type)
  {
  case DB_TYPE_STRING:
    compare_result = ansisql_strcmp ((char *) key_p, bucket_record_p);   /* <- collation-aware */
    break;
  case DB_TYPE_OBJECT:
    compare_result = oid_compare ((OID *) key_p, (OID *) bucket_record_p);  /* <- OID-keyed hash */
    break;
  /* ... condensed: DOUBLE/FLOAT/INTEGER/BIGINT/SHORT/DATE/TIME/TIMESTAMP/
     DATETIME/MONETARY all under ENABLE_UNUSED_FUNCTION ... */
  default:
    /* Unspecified key type: Directory header has been corrupted */
    er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
    return ER_EH_CORRUPTED;            /* <- non-NO_ERROR => caller returns false */
  }

*out_compare_result_p = compare_result;
return NO_ERROR;

DB_TYPE_STRING delegates to ansisql_strcmp over the NUL-terminated key bytes after the OID. (Long-key REC_BIGONE/overflow handling is compiled out under ENABLE_UNUSED_FUNCTION — the only user of record_type, hence the live path ignores it.) DB_TYPE_OBJECT delegates to oid_compare: the hash is an OID-keyed index (e.g. catalog), so both keys are OIDs. default is a corrupted key_type → ER_EH_CORRUPTED, the error §4.4 exit 2 turns into false. The result is written only on NO_ERROR; splitting status from value lets default tell “could not compare” from “compared equal”, so callers check the code.

4.6 ehash_read_oid_from_record — extracting the value by PEEK

The OID sits at offset 0 (§4.1), so the reader copies three fixed fields, not the key:

// ehash_read_oid_from_record -- src/storage/extendible_hash.c
oid_p->pageid = *(PAGEID *) record_p;
record_p += sizeof (PAGEID);
oid_p->volid = *(VOLID *) record_p;
record_p += sizeof (VOLID);
oid_p->slotid = *(PGSLOTID *) record_p;
record_p += sizeof (PGSLOTID);
return record_p;                       /* <- now points at the key bytes */

The field-by-field reads keep the encoding independent of in-memory padding; total stride is exactly sizeof(OID) (the width §4.4 skipped), so the return points at the key bytes — ehash_search (void)-discards it, the delete/dump paths reuse it. Because the record was PEEK’d, record_p aliases the page, so this copy into value_p makes the OID survive the unfix. No copy of the key is ever made — the tail is stepped over, not scanned.

4.7 The two-page-fix cost

A successful ehash_search fixes exactly two pages — root and bucket, both PGBUF_LATCH_READ — running the whole search inside those latches and copying nothing but the final OID; guard 3’s directory hole costs one fix and §4.3’s empty bucket two with no binary search, and the leaf is released before the root (§4.2). Chapter 10 covers how these latches couple with concurrent splits and merges.

4.8 Chapter summary — key takeaways

1. ehash_search has five guard branches — null args, root-fix failure, NULL_PAGEID hole, bucket-fix failure, key-absent; only the last three goto end, since only they run with the root held.
2. The invariant: every post-root-fix path drains through end:, which unfixes the bucket first, then root, each under if (ptr) so the label is reachable from any state.
3. Records are OID-first, key-second under UNANCHORED_KEEP_SEQUENCE, keeping slots in user-key order — the sole precondition for the O(log m) probe; ehash_locate_slot handles the empty-bucket edge (num_record < 1) outside the loop, since the do/while body runs before its bound is checked.
4. ehash_binary_search_bucket skips sizeof(OID) before comparing, returns the slot on a hit, and on a miss computes the insertion position (middle or middle + 1); ehash_compare_key dispatches DB_TYPE_STRING/ansisql_strcmp and DB_TYPE_OBJECT/oid_compare, default raising ER_EH_CORRUPTED — status as return code, the three-way result out-of-band.
5. ehash_read_oid_from_record extracts the value by field-by-field PEEK copy over the sizeof(OID) prefix, never scanning the key; a hit costs two READ-latched page fixes, one on a directory hole.

Chapter 5: Inserting Into a Non-Full Bucket

This chapter answers one reader question: when the target bucket has room, how is a (key, OID) pair written, and what makes ehash_insert an upsert? We trace the optimistic-S-latch orchestration in ehash_insert_helper, the record work in ehash_insert_to_bucket, and the WAL tail. We stop at the split: a full bucket returns EHASH_BUCKET_FULL and re-drives under X — that re-drive and the split are Chapter 6. Addressing is Chapter 3, the bucket binary search is Chapter 4, and the upsert/WAL rationale is in the companion’s Insert and WAL integration — RVEH_* records sections.

5.1 The two-layer latch dance: ehash_insert and ehash_insert_helper

ehash_insert is a thin wrapper: after a null guard on ehid_p/key_p it tail-calls ehash_insert_helper (..., S_LOCK, NULL) — an initial S (shared) lock on the directory.

The S_LOCK encodes optimism: most inserts land in an existing bucket with room, touching one bucket page and never the directory, so a shared root latch lets many writers proceed concurrently. lock_type drives the helper as both the optimistic first attempt and the pessimistic X retry.

ehash_insert_helper is the real driver. It notes whether the file is temporary (controls WAL emission), then resolves the key to a slot via ehash_find_bucket_vpid_with_hash (Chapter 3) under a root latch keyed off lock_type (PGBUF_LATCH_READ if S, PGBUF_LATCH_WRITE if X); a NULL return propagates the error. With the header in hand it bounds a string key before touching any bucket:

// ehash_insert_helper -- src/storage/extendible_hash.c
if (dir_header_p->key_type == DB_TYPE_STRING)
  { assert (strlen ((char *) key_p) < 256); }   /* <- max class-name length */

Invariant — string keys are ≤ 255 bytes (256 with the NUL). The production caller inserts class names, schema-capped at 255; the long-string-overflow branch is compiled out (ENABLE_UNUSED_FUNCTION). If violated, a longer key trips ehash_compose_record’s own assert (key_size <= 256), else produces a truncated record with no overflow page.

The helper then branches on whether the slot already names a bucket (Figure 5-1); two of the four leaves recurse with X_LOCK — the bridge to Chapter 6.

flowchart TD
  B["find_bucket_vpid_with_hash\nREAD if S else WRITE"] -->|root NULL| ERR["return NULL"]
  B --> C{"bucket_vpid NULL?"}
  C -->|"yes"| D{"S_LOCK?"}
  D -->|yes| R1["unfix; recurse X_LOCK"]
  D -->|"X"| E["insert_to_bucket_after_create"]
  E -->|NO_ERROR| OK["return key_p"]
  E -->|err| ERR
  C -->|"no"| F["insert_bucket_after_extend_if_need"]
  F -->|ERROR| ERR
  F -->|BUCKET_FULL| R2["unfix; recurse X_LOCK -> Ch 6"]
  F -->|SUCCESS| OK

Figure 5-1 — branch map of ehash_insert_helper. The two recurse X_LOCK leaves are the S→X promotion.

There is no in-place latch upgrade. Each promotion site unfixes the root and re-enters with X_LOCK — one when the slot is empty, one when an existing bucket is full — via the identical pgbuf_unfix_and_init + recurse call:

// ehash_insert_helper -- src/storage/extendible_hash.c
if (VPID_ISNULL (&bucket_vpid))
  {
    if (lock_type == S_LOCK)            /* slot empty under S: RESTART */
      { pgbuf_unfix_and_init (thread_p, dir_root_page_p);
        return ehash_insert_helper (thread_p, ehid_p, key_p, value_p, X_LOCK, existing_ovf_vpid_p); }
    else if (ehash_insert_to_bucket_after_create (/* ... */) != NO_ERROR)   /* under X: create (Ch 2/6) */
      { pgbuf_unfix_and_init (thread_p, dir_root_page_p); return NULL; }
  }
else
  {
    result = ehash_insert_bucket_after_extend_if_need (/* ... */ lock_type, /* ... */);
    if (result == EHASH_ERROR_OCCURRED)
      { pgbuf_unfix_and_init (thread_p, dir_root_page_p); return NULL; }
    else if (result == EHASH_BUCKET_FULL)   /* full under S: RESTART (identical recurse as above) */
      { /* ... unfix + return ehash_insert_helper (..., X_LOCK, ...) ... */ }
  }
pgbuf_unfix_and_init (thread_p, dir_root_page_p);
return (key_p);                         /* <- non-NULL key_p signals success */

Invariant — splitting requires an X latch on the directory root. A split may double the directory, so it can never run under a shared latch. The code enforces this by refusing to split under S_LOCK: ehash_insert_bucket_after_extend_if_need returns EHASH_BUCKET_FULL and the helper restarts under X_LOCK. If violated, two writers could double the directory concurrently and corrupt the fan-out.

5.2 Fixing the bucket and deciding split vs. insert: ehash_insert_bucket_after_extend_if_need

When the slot already names a bucket, the helper delegates here. Contract: fix the bucket with an X (WRITE) latch, attempt the insert, and — only if full and under X — split and retry into the correct half. Returns one of three EHASH_RESULTs (Figure 5-1):

// ehash_insert_bucket_after_extend_if_need -- src/storage/extendible_hash.c
bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid, bucket_vpid_p, PGBUF_LATCH_WRITE);  /* always X */
if (bucket_page_p == NULL)
  { return EHASH_ERROR_OCCURRED; }
result = ehash_insert_to_bucket (thread_p, ehid_p, /* ... */ bucket_page_p, /* ... */);
if (result == EHASH_BUCKET_FULL)
  {
    if (lock_type == S_LOCK)            /* cannot split under S: bubble up for the X restart */
      { pgbuf_unfix_and_init (thread_p, bucket_page_p); return EHASH_BUCKET_FULL; }
    // ... split (Ch 6): ehash_extend_bucket -> &new_bit, re-insert into
    //     target = new_bit ? sibling_page_p : bucket_page_p; unfix sibling ...
  }
pgbuf_unfix_and_init (thread_p, bucket_page_p);
return result;

The bucket page is always X-latched here, even on the optimistic S attempt — the S in the dance is the directory latch; a bucket write must be exclusive regardless. new_bit and ehash_extend_bucket are Chapter 6. The non-full case for this chapter: ehash_insert_to_bucket returns EHASH_SUCCESSFUL_COMPLETION, the EHASH_BUCKET_FULL block is skipped, and success propagates back.

5.3 The record-level engine: ehash_insert_to_bucket

This is where the upsert lives. The function locates the key with ehash_locate_slot, then takes one of two paths; Figure 5-2 traces every branch.

flowchart TD
  B["locate_slot -> slot_no"] --> C{"key found?"}
  C -->|"yes upsert"| E["copy old as pre-image\nwrite_oid overwrites OID in place"]
  E -->|alloc fail| ERR["return ERROR_OCCURRED"]
  E --> LOG
  C -->|"no insert"| F["compose_record"]
  F -->|err| ERR
  F --> G["spage_insert_at(slot_no)"]
  G -->|SP_DOESNT_FIT| FULL["free; return BUCKET_FULL"]
  G -->|"other != SP_SUCCESS"| ERR
  G -->|SP_SUCCESS| LOG
  LOG["emit WAL: undo logical + redo physical\n(branches on is_replaced_oid; see 5.5)"] --> Z["free; set_dirty; return SUCCESS"]

Figure 5-2 — every branch of ehash_insert_to_bucket. The WAL node expands in §5.5.

Step 1 — locate. ehash_locate_slot returns true/false and writes slot_no. It computes num_record = spage_number_of_records (bucket_page_p) - 1; when that is < 1 the bucket holds only its 1-byte EHASH_BUCKET_HEADER (the local_depth byte from Chapter 2), so it takes the empty-bucket shortcut (slot_no = first_slot_id + 1, the slot right after the header) and returns false. Otherwise it forwards to ehash_binary_search_bucket (Chapter 4). On false, slot_no is the insertion position that keeps the bucket sorted.

Step 2a — the found path (upsert / OID replacement). The existing record is peeked, copied into a freshly allocated bucket_recdes (the pre-image, for undo), then the OID is overwritten in place in the live record:

// ehash_insert_to_bucket -- src/storage/extendible_hash.c
if (ehash_locate_slot (thread_p, bucket_page_p, key_type, key_p, &slot_no) == true)
  {
    (void) spage_get_record (thread_p, bucket_page_p, slot_no, &old_bucket_recdes, PEEK);
    bucket_record_p = (char *) old_bucket_recdes.data;
    is_replaced_oid = true;
    if (ehash_allocate_recdes (&bucket_recdes, old_bucket_recdes.length, old_bucket_recdes.type) == NULL)
      { return EHASH_ERROR_OCCURRED; }
    memcpy (bucket_recdes.data, bucket_record_p, bucket_recdes.length);   /* pre-image for undo */
    (void) ehash_write_oid_to_record (bucket_record_p, value_p);          /* <- in-place OID overwrite */
  }

The replacement is byte-surgical — only the leading sizeof(OID) bytes change, so the redo can be a tiny sizeof(OID) patch (§5.5). Setting is_replaced_oid = true before the alloc check is harmless: on alloc failure the function returns without logging.

Step 2b — the not-found path (fresh insert). The record is composed by ehash_compose_record (§5.4), then handed to spage_insert_at at the chosen slot, whose result is the chapter’s hinge:

// ehash_insert_to_bucket -- src/storage/extendible_hash.c
else   /* not found: ehash_compose_record (..., &bucket_recdes) into bucket_recdes, then: */
  {
    success = spage_insert_at (thread_p, bucket_page_p, slot_no, &bucket_recdes);
    if (success != SP_SUCCESS)
      {
        ehash_free_recdes (&bucket_recdes);
        if (success == SP_DOESNT_FIT)
          { return EHASH_BUCKET_FULL; }   /* <- only "normal" non-success -> split (Ch 6) */
        er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_GENERIC_ERROR, 0);
        return EHASH_ERROR_OCCURRED;       /* every other failure is fatal */
      }
  }

Invariant — EHASH_BUCKET_FULL is reserved for the one recoverable failure. Only SP_DOESNT_FIT is benign (page out of room, resolved by a split); every other non-SP_SUCCESS is a fatal ER_GENERIC_ERROR → EHASH_ERROR_OCCURRED. If violated, §5.2’s retry would split and re-insert endlessly against a broken page. The upsert path can never report full — it changes no lengths.

5.4 Building the record bytes: ehash_compose_record, ehash_write_key_to_record, ehash_write_oid_to_record

A bucket record is (OID, key). ehash_compose_record sizes it (sizeof(OID) + key_size) and allocates; ehash_write_key_to_record sets the record type (always REC_HOME here), writes the OID first, then copies the key body — memcpy for a string, *(OID *) assignment for DB_TYPE_OBJECT, a corruption fatal otherwise:

// ehash_compose_record -- src/storage/extendible_hash.c
if (key_type == DB_TYPE_STRING)
  { key_size = (short) strlen ((char *) key_p) + 1; assert (key_size <= 256); }  /* +\0; 2nd §5.1 guard */
else
  { key_size = ehash_get_key_size (key_type); if (key_size < 0) return ER_FAILED; }  /* unknown type */
if (ehash_allocate_recdes (recdes_p, sizeof (OID) + key_size, REC_HOME) == NULL) { return ER_FAILED; }
return ehash_write_key_to_record (recdes_p, key_type, key_p, key_size, value_p, is_long_str);

// ehash_write_key_to_record -- src/storage/extendible_hash.c
recdes_p->type = is_long_str ? REC_BIGONE : REC_HOME;
record_p = ehash_write_oid_to_record (recdes_p->data, value_p);   /* OID first: pageid, volid, slotid */
switch (key_type)
  {
  case DB_TYPE_STRING:  memcpy (record_p, (char *) key_p, key_size); break;  /* incl. NUL */
  case DB_TYPE_OBJECT:  *(OID *) record_p = *(OID *) key_p; break;
  // ... other fixed-width cases are #if ENABLE_UNUSED_FUNCTION ...
  default:              /* <- fatal: unknown type */
    er_set (ER_FATAL_ERROR_SEVERITY, ARG_FILE_LINE, ER_EH_CORRUPTED, 0);
    ehash_free_recdes (recdes_p); return ER_EH_CORRUPTED;
  }

ehash_write_oid_to_record advances record_p past pageid, volid, slotid and returns it so callers keep appending.

Invariant — the OID occupies the first sizeof(OID) bytes of every bucket record, in (pageid, volid, slotid) order. The upsert overwrite reuses the same writer over the same leading bytes; §5.5’s RVEH_REPLACE redo records exactly sizeof(OID) there. If violated, upsert corrupts the key and the Chapter 4 comparators (which skip sizeof(OID) to reach the key) read garbage.

5.5 The WAL tail: logical-undo, physical-redo, and pgbuf_set_dirty

After modifying the page, ehash_insert_to_bucket allocates log_recdes at bucket_recdes.length + sizeof(EHID) and fills it as EHID + bucket_recdes. Which record bucket_recdes holds is the subtlety: on the upsert path it is the pre-image copied at §5.3 Step 2a (so the undo carries the old OID to restore); on the fresh-insert path it is the new record just slotted. The EHID prefix makes the undo logical (replayed against the file, not a frozen page address); the redo stays physical. Both halves branch on is_replaced_oid:

// ehash_insert_to_bucket -- src/storage/extendible_hash.c
log_record_p = ehash_write_ehid_to_record (log_recdes.data, ehid_p);   /* <- EHID makes undo logical */
memcpy (log_record_p, bucket_recdes.data, bucket_recdes.length);
if (!is_temp)   /* UNDO: pgptr NULL -> page-agnostic. DELETE restores old oid; INSERT deletes key */
  log_append_undo_data2 (thread_p, is_replaced_oid ? RVEH_DELETE : RVEH_INSERT,
                         &ehid_p->vfid, NULL, /* ... */ log_recdes.data);
// ... REDO half: physical, branches on is_replaced_oid ...
if (is_replaced_oid)
  {
    if (!is_temp)   /* byte offset; only the OID-sized patch */
      log_append_redo_data2 (thread_p, RVEH_REPLACE, &ehid_p->vfid, bucket_page_p,
                             (int) (old_bucket_recdes.data - bucket_page_p), sizeof (OID),
                             old_bucket_recdes.data);
  }
else
  {
    // ... prepend rec type as a short (dodges alignment), then the record bytes ...
    if (!is_temp)   /* slot id */
      log_append_redo_data2 (thread_p, RVEH_INSERT, &ehid_p->vfid, bucket_page_p, slot_no,
                             log_recdes.length, log_recdes.data);
  }
// ... free both RECDES buffers ...
pgbuf_set_dirty (thread_p, bucket_page_p, DONT_FREE);   /* caller still holds latch */
return EHASH_SUCCESSFUL_COMPLETION;

Upsert undo is RVEH_DELETE with the pre-image (rollback re-installs the prior value); fresh-insert undo is RVEH_INSERT (rollback deletes the key). The redo mirrors this on the same flag: upsert’s RVEH_REPLACE payload is old_bucket_recdes.data — the live record bytes, already overwritten with the new OID in §5.3 — logged at offset old_bucket_recdes.data - bucket_page_p for exactly sizeof(OID); fresh-insert’s RVEH_INSERT is keyed by slot_no. DONT_FREE is required because §5.2’s caller still owns the X latch. For an is_temp hash all four log_append_* calls are skipped (no crash recovery), but pgbuf_set_dirty still runs.

Invariant — logical undo, physical redo, both per-record. Undo carries no page pointer (NULL) but does carry EHID + full record, so it replays against the file even if the bucket has since moved or split; redo carries a concrete page + offset/slot but only the changed bytes. If violated: a physical undo breaks after a concurrent split relocates the record; a logical redo forces re-resolving the bucket on every recovery pass.

5.6 Chapter summary — key takeaways

1. ehash_insert starts optimistic — S_LOCK on the root, betting the insert touches one existing non-full bucket and never the directory.
2. S→X promotion is by restart, not upgrade. On a structural need (empty slot or full bucket) the helper unfixes the root and recurses with X_LOCK; the bucket page is always X-latched regardless.
3. EHASH_BUCKET_FULL is the clean “go split” signal — only SP_DOESNT_FIT produces it; every other slotted-page failure is fatal, and the upsert path can never report full.
4. Insert is an upsert via in-place OID overwrite — when ehash_locate_slot finds the key, the code saves a pre-image then overwrites only the leading sizeof(OID) bytes; key bytes and length stay fixed.
5. Every bucket record is (OID, key), OID first (sizeof(OID) + key_size). That fixed leading offset is what the upsert overwrite and RVEH_REPLACE redo both target.
6. Undo is logical (NULL page + EHID + full record), redo is physical (page + offset/slot, changed bytes only) — RVEH_DELETE/RVEH_INSERT undo, RVEH_REPLACE/RVEH_INSERT redo.
7. The string key is bounded at 255 bytes, asserted twice; long-string machinery is compiled out. The split (ehash_extend_bucket, new_bit half-selection) is Chapter 6.

Chapter 6: Splitting a Full Bucket and Raising Local Depth

When ehash_insert_to_bucket returns EHASH_BUCKET_FULL, the key still belongs in that bucket by hash prefix but there is no room. CUBRID splits: it raises the bucket’s local depth, allocates a sibling, and redistributes records by the bit that now distinguishes them. This chapter traces the split half of ehash_extend_bucket — up to (not including) the directory-size decision new_local_depth > dir_header_p->depth, which Chapter 7 owns. For the local/global-depth model, see the companion.

6.1 The system-op bracket: ehash_extend_bucket

ehash_extend_bucket is the transactional envelope: it opens a nested system op, and on any failure aborts it so the half-finished split is physically undone:

// ehash_extend_bucket -- src/storage/extendible_hash.c
if (!is_temp) { log_sysop_start (thread_p); }      /* <- atomic bracket for the whole split+connect */

sibling_page_p = ehash_split_bucket (thread_p, dir_header_p, bucket_page_p, key_p, &old_local_depth,
                                     &new_local_depth, &sibling_vpid, is_temp);
if (sibling_page_p == NULL)
  {
    if (!is_temp) { log_sysop_abort (thread_p); }  /* <- split failed: roll back, return NULL */
    return NULL;
  }

*out_new_bit_p = GETBIT (hash_key, new_local_depth);   /* <- which side does the triggering key land on? */
ehash_adjust_local_depth (thread_p, ehid_p, dir_root_page_p, dir_header_p, old_local_depth, -1, is_temp);
ehash_adjust_local_depth (thread_p, ehid_p, dir_root_page_p, dir_header_p, new_local_depth,  2, is_temp);

Invariant (split atomicity): every page mutated between log_sysop_start and log_sysop_commit is either all-committed or all-undone, enforced by routing every error exit through log_sysop_abort. The post-split path has four such exits (one in the directory-expand branch, three in the connect-bucket code of Chapter 7) plus the ehash_split_bucket failure above — five aborts total. A missed abort would let the sysop commit with a sibling allocated but unreferenced — a permanent leak.

ehash_split_bucket runs first and is the only step in the split half that can fail (it deallocates its own sibling on failure, 6.6). Everything after it is unconditional and infallible, so sibling_page_p == NULL is the only early return here. is_temp threads through every logging decision: for a temporary hash the sysop bracket and all logging collapse to no-ops while the page mutations still happen.

flowchart TD
  D["ehash_split_bucket"] --> E{"sibling == NULL?"}
  E -- yes --> F["log_sysop_abort if not temp; return NULL"]
  E -- no --> H["out_new_bit; adjust(old,-1); adjust(new,+2)"]
  H --> J["dir-size branch -> Ch 7"]

Figure 6-1. Control flow of the split half. The single early return is the split failure; the chapter stops at node J.

6.2 ehash_split_bucket — logging the pre-split image and choosing the new depth

ehash_split_bucket reports back old_local_depth, new_local_depth, and the sibling VPID, and keeps the original bucket page fixed (the caller inserts the triggering key later), only setting it dirty. Its first action captures the entire pre-split bucket as undo, then reads the header and chooses the new depth:

// ehash_split_bucket -- src/storage/extendible_hash.c
if (!is_temp)
  log_append_undo_data2 (thread_p, RVEH_REPLACE, &dir_header_p->bucket_file, bucket_page_p, 0, DB_PAGESIZE,
                         bucket_page_p);                   /* <- full-page undo image, before split */
num_records = spage_number_of_records (bucket_page_p);
if (spage_next_record (bucket_page_p, &first_slot_id, &recdes, PEEK) != S_SUCCESS)   /* <- slot 0 = header */
  { er_set (...ER_EH_CORRUPTED...); return NULL; }          /* <- corruption: caller aborts sysop */

bucket_header_p = (EHASH_BUCKET_HEADER *) recdes.data;
*out_old_local_depth_p = bucket_header_p->local_depth;
if (ehash_find_first_bit_position (thread_p, dir_header_p, bucket_page_p, bucket_header_p, key_p, num_records,
                                   first_slot_id, out_old_local_depth_p, out_new_local_depth_p) != NO_ERROR)
  { return NULL; }                                          /* <- depth-choice failure: caller aborts sysop */

RVEH_REPLACE is a whole-page logical-replace type: the undo image is the full DB_PAGESIZE page before the split, so abort restores the bucket exactly. The first spage_next_record (with first_slot_id == -1) fetches slot 0, the EHASH_BUCKET_HEADER (Chapter 1). This excerpt exposes the first three NULL-return branches — the silent undo-log step, the corruption check (ER_EH_CORRUPTED), and the ehash_find_first_bit_position failure (6.3) — each aborting the caller’s sysop.

6.3 ehash_find_first_bit_position — the smallest separating depth

CUBRID does not blindly set new_local_depth = old_local_depth + 1. If every record shares the same bit at old+1, bumping by one moves zero records — the overflow persists and the next insert splits forever. So ehash_find_first_bit_position finds the first bit beyond the current depth where records disagree:

// ehash_find_first_bit_position -- src/storage/extendible_hash.c
check_bit = 1 << (EHASH_HASH_KEY_BITS - bucket_header_p->local_depth - 1);   /* <- bit just past local_depth */
first_hash_key = ehash_hash (key_p, dir_header_p->key_type);   /* <- pseudo key of the NEW (triggering) key */
for (slot_id = first_slot_id + 1; slot_id < num_recs; slot_id++)
  {
    if (spage_get_record (...) != S_SUCCESS)
      { er_set (...ER_EH_CORRUPTED...); return ER_EH_CORRUPTED; }   /* <- distinct code: corruption */
    if (ehash_get_pseudo_key (..., &next_hash_key) != NO_ERROR)
      { return ER_FAILED; }                                /* <- distinct code: pseudo-key failure */
    difference = (first_hash_key ^ next_hash_key) | difference;   /* <- accumulate all differing bits */
    if (difference & check_bit) { break; }                        /* <- earliest possible split bit found */
  }

The XOR is 1 where the new key and that record disagree; OR-ing into difference accumulates the union. The break is an optimization: once difference has a 1 in check_bit (the bit just past the old depth) no later record can shrink the answer. The first loop has two distinct-code early returns, ER_EH_CORRUPTED and ER_FAILED. The second loop walks outward from local_depth + 1 for the leftmost set bit:

// ehash_find_first_bit_position -- src/storage/extendible_hash.c (continued)
bit_position = *out_old_local_depth_p + 1;       /* <- default if loop finds nothing within range */
for (i = bucket_header_p->local_depth + 1; i <= EHASH_HASH_KEY_BITS; i++)
  {
    if (difference & check_bit) { bit_position = i; break; }   /* <- first disagreeing depth = new depth */
    check_bit >>= 1;                               /* <- walk one bit toward the LSB */
  }
bucket_header_p->local_depth = bit_position;       /* <- mutate the in-page header */
*out_new_local_depth_p = bit_position;

Invariant (separating depth): new_local_depth is the smallest depth > old_local_depth at which the new key’s pseudo key differs from at least one record, or old_local_depth + 1 as fallback — guaranteeing the new key a non-full home. What breaks if violated: too small, the recursion in ehash_insert_bucket_after_extend_if_need never terminates; too large, the directory over-expands and wastes entries.

The in-page bucket_header_p->local_depth is raised immediately (its undo image was logged in 6.2). check_bit is shared by both loops — the first leaves it at the old+1 bit, the second re-shifts from there.

6.4 ehash_get_pseudo_key — extracting a record’s hash key

Both the scan and the redistribution call ehash_get_pseudo_key. Records are OID + key bytes, so it skips the OID and re-hashes: hash_key = ehash_hash ((char *) recdes_p->data + sizeof (OID), key_type) (the REC_BIGONE branch is compiled out under ENABLE_UNUSED_FUNCTION). CUBRID re-derives the pseudo key on demand — the same 32-bit value the directory addresses with (Chapter 3); the split consults deeper bits.

6.5 ehash_distribute_records_into_two_bucket — partitioning by the new bit

Records whose pseudo key has a 1 at new_local_depth go to the sibling; 0-records stay. The loop walks the slots once:

// ehash_distribute_records_into_two_bucket -- src/storage/extendible_hash.c
for (slot_id = i = first_slot_id + 1; i < num_recs; i++)
  {
    if (spage_get_record (..., slot_id, &recdes, PEEK) != S_SUCCESS) { return ER_FAILED; }
    if (ehash_get_pseudo_key (..., &recdes, ..., &hash_key) != NO_ERROR) { return ER_FAILED; }
    if (GETBIT (hash_key, bucket_header_p->local_depth))     /* <- local_depth already set to new depth */
      {                                                      /* <- 1-bit: move to sibling */
        success = spage_insert (thread_p, sibling_page_p, &recdes, &sibling_slot_id);
        if (success != SP_SUCCESS) { er_set (...ER_GENERIC_ERROR...); return ER_FAILED; }  /* <- caller deallocs */
        (void) spage_delete (thread_p, bucket_page_p, slot_id);   /* <- slot_id NOT advanced: next slides in */
      }
    else { slot_id++; }                                      /* <- 0-bit: keep, advance slot */
  }

Dual cursor: i counts records examined, slot_id is the physical slot. On a move, spage_delete compacts so the next record takes the same slot_id (no increment); on a keep, slot_id advances. The spage_insert failure (debug comment: “should never happen”) is the only error branch; it returns ER_FAILED and 6.6 cleans up.

Invariant (order preservation): both halves stay sorted by user key — the single forward pass plus UNANCHORED_KEEP_SEQUENCE slots append moved records in ascending order, and compaction never reorders survivors. What breaks if violated: ehash_binary_search_bucket (Chapter 4) would miss keys, corrupting lookups.

6.6 The sibling page: file_alloc + ehash_initialize_bucket_new_page

ehash_split_bucket allocates the sibling through ehash_initialize_bucket_new_page, passing a 3-byte arg blob:

// ehash_split_bucket -- src/storage/extendible_hash.c
init_bucket_data[0] = dir_header_p->alignment;
init_bucket_data[1] = *out_new_local_depth_p;          /* <- sibling is born at the new depth */
init_bucket_data[2] = is_temp;
error_code = file_alloc (..., ehash_initialize_bucket_new_page, init_bucket_data, sibling_vpid_p, &sibling_page_p);
if (error_code != NO_ERROR) { ASSERT_ERROR (); return NULL; }          /* <- alloc failed: caller aborts */
if (sibling_page_p == NULL) { assert_release (false); return NULL; }   /* <- defensive NULL check */

if (ehash_distribute_records_into_two_bucket (...) != NO_ERROR)
  {
    pgbuf_unfix_and_init (thread_p, sibling_page_p);
    if (file_dealloc (..., sibling_vpid_p, FILE_EXTENDIBLE_HASH) != NO_ERROR) { ASSERT_ERROR (); }
    VPID_SET_NULL (sibling_vpid_p);
    return NULL;                                          /* <- sibling cleaned up; caller aborts sysop */
  }
if (!is_temp)
  {
    log_append_redo_data2 (..., RVEH_REPLACE, ..., bucket_page_p, 0, DB_PAGESIZE, bucket_page_p);    /* both */
    log_append_redo_data2 (..., RVEH_REPLACE, ..., sibling_page_p, 0, DB_PAGESIZE, sibling_page_p);  /* pages */
  }
pgbuf_set_dirty (thread_p, sibling_page_p, DONT_FREE);   /* <- bucket_page_p set dirty likewise */
return sibling_page_p;

The callback initializes a UNANCHORED_KEEP_SEQUENCE slotted page (source of the 6.5 order invariant), writes the bucket header with local_depth = depth as slot 0, and logs the init args as RVEH_INIT_BUCKET undoredo — not a full page, since file-layer undo covers allocation. So the original bucket carries RVEH_REPLACE undo (6.2) + redo (here) and the sibling RVEH_INIT_BUCKET undoredo + RVEH_REPLACE redo: a crash replays both on redo; an abort restores the original and reclaims the sibling. The distribution-failure branch deallocates the sibling and nulls the out-VPID itself.

6.7 ehash_adjust_local_depth and out_new_bit

The histogram local_depth_count[] (Chapter 1) must reflect the split: one bucket left old_local_depth, two now sit at new_local_depth — hence -1 then +2:

// ehash_adjust_local_depth -- src/storage/extendible_hash.c
dir_header_p->local_depth_count[depth] += delta;          /* <- mutate the histogram bucket */
pgbuf_set_dirty (thread_p, dir_root_page_p, DONT_FREE);
offset = CAST_BUFLEN ((char *) (dir_header_p->local_depth_count + depth) - (char *) dir_root_page_p);
redo_inc = delta;  undo_inc = -delta;                     /* <- exact inverse for undo */
if (!is_temp)
  {
    log_append_undoredo_data2 (thread_p, RVEH_INC_COUNTER, &ehid_p->vfid, dir_root_page_p, offset, sizeof (int),
                               sizeof (int), &undo_inc, &redo_inc);     /* <- delta-style log */
  }

RVEH_INC_COUNTER is a delta record, not value-replace: redo is +delta, undo is -delta, applied to the int at offset (the offset of local_depth_count[depth] in the root page). The inverse delta reverses the increment regardless of intervening values, so recovery is order-independent. Chapter 9’s shrink logic reads this histogram.

The other output, *out_new_bit_p = GETBIT (hash_key, new_local_depth) (the 6.1 excerpt), is computed before the adjusts; hash_key is the triggering key’s pseudo key, so it lands in whichever half that bit selects (the 6.5 rule). The caller ehash_insert_bucket_after_extend_if_need reads it for the retry target — 1 selects the sibling, 0 the residual — and by the separating-depth invariant (6.3) that half has room. Control then reaches the new_local_depth > dir_header_p->depth test of Chapter 7.

6.8 Chapter summary — key takeaways

1. ehash_extend_bucket wraps the split in a log_sysop_start / log_sysop_commit bracket and routes every failure through log_sysop_abort (five aborts, one in the split half); is_temp collapses the bracket and logging to no-ops.
2. ehash_split_bucket logs the full pre-split page as RVEH_REPLACE undo, then both pages as redo; it has three NULL-return branches before allocation (undo step, spage_next_record corruption, ehash_find_first_bit_position failure) and keeps the original bucket fixed.
3. CUBRID does not blindly do old_local_depth + 1. ehash_find_first_bit_position XORs each record’s pseudo key against the new key and picks the smallest disagreeing depth; its scan returns two codes (ER_EH_CORRUPTED, ER_FAILED).
4. ehash_distribute_records_into_two_bucket partitions by the new_local_depth bit with a dual cursor: slot_id holds still on a move (compaction slides the next record down) and advances on a keep, keeping both halves sorted.
5. The sibling is born at the new depth via file_alloc + ehash_initialize_bucket_new_page (RVEH_INIT_BUCKET); on distribution failure it file_deallocs the sibling and nulls the out-VPID.
6. Two delta-logged ehash_adjust_local_depth calls (-1 at old, +2 at new) emit RVEH_INC_COUNTER with inverse undo/redo deltas, so recovery is order-independent.
7. out_new_bit = GETBIT(hash_key, new_local_depth) selects the retry half (1 -> sibling, 0 -> residual), which the separating-depth invariant guarantees has room.

Chapter 7: Doubling the Directory and Connecting Bucket Pointers

Chapter 6 traced the split half of ehash_extend_bucket — up to (not including) the directory-size decision new_local_depth > dir_header_p->depth, which it explicitly hands to this chapter. We resume the instant ehash_split_bucket has redistributed records into a freshly allocated sibling and reported old_local_depth / new_local_depth. This chapter traces the directory-mutation tail: what happens when a split raises a bucket’s local depth past the global depth, forcing the directory to double, and how the pointer ranges that addressed the single old bucket are split between original and sibling. The high-level companion (cubrid-extendible-hash.md, sections Insert — ehash_insert and WAL integration — RVEH_* records) covers why the directory doubles when local > global; this chapter traces every branch of the three implementing functions, every field of the recovery record they emit, and the bit arithmetic that moves the pointers.

The standing invariant this chapter restores. Extendible hashing maintains, at all times between operations, that every bucket’s local depth is no greater than the directory’s global depth:

Invariant (depth ceiling): for every bucket, local_depth <= dir_header_p->depth (global depth). A split that raises a bucket to new_local_depth > depth transiently violates it; ehash_expand_directory restores it by lifting depth to new_local_depth so the directory regains the resolution to address original and sibling separately. What breaks if violated: with local_depth > depth the directory has fewer than 2^local_depth slots — two distinct local prefixes would collide on one slot, so one of {original, sibling} would be unaddressable and its keys unreachable.

7.1 The tail of ehash_extend_bucket — orchestration

When control reaches the tail a sibling page exists. It first captures the deciding bit *out_new_bit_p = GETBIT (hash_key, new_local_depth), then re-balances the per-depth counters with ehash_adjust_local_depth (old_local_depth count -1, new_local_depth count +2). Then it optionally doubles the directory and issues up to three ehash_connect_bucket calls:

// ehash_extend_bucket -- src/storage/extendible_hash.c
// every error block below is identical: pgbuf_unfix_and_init(sibling); if(!is_temp) log_sysop_abort; return NULL;
if (new_local_depth > dir_header_p->depth)              /* <- local outgrew global: must double */
  if (ehash_expand_directory (..., new_local_depth, is_temp) != NO_ERROR) { /* abort, return NULL */ }

if ((new_local_depth - old_local_depth) > 1)            /* <- depth jumped by more than 1 */
  {
    /* First, set all of them to NULL_PAGEID */
    if (ehash_connect_bucket (..., old_local_depth, hash_key, &null_vpid, is_temp) != NO_ERROR) { /* abort */ }
    hash_key = CLEARBIT (hash_key, new_local_depth);    /* <- new MSB 0: lower half */
    if (ehash_connect_bucket (..., new_local_depth, hash_key, bucket_vpid, is_temp) != NO_ERROR) { /* abort */ }
  }

hash_key = SETBIT (hash_key, new_local_depth);          /* <- new MSB 1: upper half */
if (ehash_connect_bucket (..., new_local_depth, hash_key, &sibling_vpid, is_temp) != NO_ERROR) { /* abort */ }

flowchart TD
  A["enter tail<br/>sibling fixed, depths reported"] --> B["out_new_bit = GETBIT(hash_key, new_local_depth)<br/>adjust counters: old -1, new +2"]
  B --> C{"new_local_depth ><br/>global depth?"}
  C -->|yes| D["ehash_expand_directory<br/>double, depth := new_local_depth"]
  C -->|no| E
  D --> E{"new_local_depth -<br/>old_local_depth > 1?"}
  E -->|yes| F["connect old_local_depth -> null_vpid<br/>NULL the stale wide range"]
  F --> G["hash_key = CLEARBIT(new_local_depth)<br/>connect lower half -> original"]
  G --> H
  E -->|no, normal +1| H["hash_key = SETBIT(new_local_depth)<br/>connect upper half -> sibling"]
  H --> I["log_sysop_commit<br/>return sibling page"]

Figure 7-1. The directory-mutation tail of ehash_extend_bucket. Two orthogonal gates (doubling, multi-step NULL-then-relink) precede a final sibling connect that always runs. Every error block — collapsed in the excerpt — unfixes the sibling and routes through log_sysop_abort.

The doubling gate fires only when the directory lacks the resolution to give original and sibling separate addresses; otherwise it is skipped and the connect calls re-target existing slots. The multi-step gate fires only when the split raised local depth by more than one — the slots between the lower and upper halves then address prefixes belonging to neither bucket and must be NULLed first. On a normal +1 split this branch is skipped: the final sibling connect handles the upper half while the lower half still points at the original. *out_new_bit_p is captured before any mutation (§7.6). Each error block (shown collapsed) aborts the outer log_sysop_start sysop, rolling the partial mutation back via the undo records §7.3 and §7.5 emit.

Invariant (directory pointer coverage): after the tail completes, every slot in the affected range points at exactly one of {original, sibling}; none still points at a stale combined region. In the >1 branch the NULL pass guarantees no slot retains the old wide mapping before the narrow halves are re-stamped, and the sibling connect closes the upper half. What breaks if violated: skipping the NULL pass on a >1 jump would make lookups for an intermediate prefix resolve to the wrong bucket and silently lose or mis-route keys.

7.2 EHASH_REPETITION — the run-length connect record

ehash_connect_bucket may stamp thousands of identical pointers onto one page. Rather than one WAL record per pointer, CUBRID logs a single run-length descriptor per page: “the same vpid, repeated count times.”

// ehash_repetition -- src/storage/extendible_hash.c
struct ehash_repetition          /* typedef'd EHASH_REPETITION */
{
  /* The "vpid" is repeated "count" times */
  VPID vpid;
  int count;
};

Field	Role	Why it exists
vpid	The bucket page id (volid + pageid) every slot in this run is set to; a real bucket, or null_vpid ({NULL_VOLID, NULL_PAGEID}) for the NULL pass.	The value written into each EHASH_DIR_RECORD.bucket_vpid. Carried once, it lets recovery replay the whole run from a constant-size record.
count	Consecutive EHASH_DIR_RECORD slots, from recv->offset, that receive vpid; computed as bef_length / sizeof(EHASH_DIR_RECORD).	Converts the byte range into a slot count so the redo handler loops without re-deriving page layout — making the record O(1) per page instead of O(pointers).

EHASH_REPETITION carries the same meaning in payload and handler — no role matrix; its only subtlety is vpid doubling as a sentinel (null_vpid is a legitimate run target for the NULL pass). The RVEH_CONNECT_BUCKET record pairs a literal pre-image undo (bef_length bytes at start_offset) with this constant-size redo. The redo handler ehash_rv_connect_bucket_redo copies the payload, loops count times from recv_p->offset, and writes repetition.vpid only where !VPID_EQ of slot and target — skipping already-correct slots, making replay idempotent.

7.3 ehash_expand_directory — doubling in a single backward pass

The directory is a logically contiguous array of EHASH_DIR_RECORD across the EHID file’s pages (page 0 shares space with the header). Doubling from depth d to d′ makes each old pointer appear exp_times = 2^(d′-d) times, done in place, walking from the last pointer backward, so no record is overwritten before it is copied. The header’s depth field is lifted to new_depth at the end — the assignment that discharges the §7.0 depth-ceiling invariant.

Sizing and allocation. It fixes the header (write latch) and reads the page count (file_get_num_user_pages failure is the earliest error path: ASSERT_ERROR, unfix header, return error_code, before any mutation), computes old_ptrs = 1 << depth, exp_times = 1 << (new_depth - depth), new_ptrs = old_ptrs * exp_times, and locates the last old and last new pointer via ehash_dir_locate.

// ehash_expand_directory -- src/storage/extendible_hash.c
// #ifdef EHASH_DEBUG: check_pages != old_pages -> unfix header, ER_EH_ROOT_CORRUPTED, return ER_FAILED
needed_pages = new_pages - old_pages;
if (needed_pages > 0)                                  /* <- N pages allocated in one call */
  if (file_alloc_multiple (..., ehash_initialize_dir_new_page, &is_temp, needed_pages, NULL) != NO_ERROR)
    { /* ASSERT_ERROR; unfix header; return error_code */ }

The EHASH_DEBUG branch raises ER_EH_ROOT_CORRUPTED / ER_FAILED on check_pages != old_pages (a no-op in release builds). The needed_pages > 0 branch is the only one touching disk: file_alloc_multiple allocates all pages and runs ehash_initialize_dir_new_page (§7.4) on each; on failure it unfixes the header and returns. Otherwise nothing is allocated.

Initial page logging before the loop. It fixes the last old page as source cursor and the last new slot’s page as destination. A NULL source unfixes the header; a NULL destination unfixes both header and source first. A reused destination old page (new_dir_nth_page <= old_pages) has its RVEH_REPLACE undo pre-image logged once here. Both cursors then descend in lockstep: source (old_dir_nth_page, old_dir_offset), destination (new_dir_nth_page, new_dir_offset).

// ehash_expand_directory (copy loop) -- src/storage/extendible_hash.c
for (j = old_ptrs; j > 0; j--)
  {
    if (old_dir_offset < 0)                  /* <- off top of source page: step back */
      {
        pgbuf_unfix_and_init (thread_p, old_dir_page_p);
        old_dir_page_p = ehash_fix_nth_page (..., --old_dir_nth_page, ...);
        if (old_dir_page_p == NULL) { /* unfix header+new, return ER_FAILED */ }
        old_dir_offset = old_dir_nth_page ? EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE : ..._IN_FIRST_PAGE;
      }
    for (i = 1; i <= exp_times; i++)         /* emit exp_times copies of this source record */
      {
        if (new_dir_offset < 0)              /* <- off top of dest page */
          {
            if (!is_temp)                    /* redo-log the finished dst page */
              log_append_redo_data2 (..., RVEH_REPLACE, ..., new_dir_page_p, 0, DB_PAGESIZE, ...);
            pgbuf_set_dirty (thread_p, new_dir_page_p, FREE);
            new_dir_page_p = ehash_fix_nth_page (..., --new_dir_nth_page, ...);
            if (new_dir_page_p == NULL) { /* unfix header+old, return ER_FAILED */ }
            if (new_dir_nth_page <= old_pages && !is_temp)   /* pre-image of a reused page */
              log_append_undo_data2 (..., RVEH_REPLACE, ..., new_dir_page_p, ...);
            new_dir_offset = new_dir_nth_page ? EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE : ..._IN_FIRST_PAGE;
          }
        if ((char *) new_dir_page_p + new_dir_offset != (char *) old_dir_page_p + old_dir_offset)
          memcpy (... new ..., ... old ..., sizeof (EHASH_DIR_RECORD));   /* <- skip self-copy */
        new_dir_offset -= sizeof (EHASH_DIR_RECORD);
      }
    old_dir_offset -= sizeof (EHASH_DIR_RECORD);
  }

A source-step fix failure unfixes header+destination; a destination-step failure unfixes header+source. Finishing: depth is set to new_depth, the header-bearing destination page gets a RVEH_REPLACE redo after-image (when !is_temp), all pages unfixed.

Invariant (backward, non-overwriting copy order): the destination byte address is always at or above the source byte address, so a source record is read before any pass writes over it. Since new_ptrs >= old_ptrs and both cursors descend together, a front-to-back walk would clobber a not-yet-copied pointer; the new != old guard skips the one coincident self-copy. What breaks if violated: copying forward would overwrite source pointers still owed to later destination slots, corrupting the doubled directory.

Invariant (RVEH_REPLACE undo only for reused pages): only destination pages with nth_page <= old_pages get an undo pre-image. A freshly allocated page has no prior content to restore (ehash_initialize_dir_new_page already logged its creation). What breaks if violated: omitting undo for a reused page would lose rollback ability; logging undo for a fresh page would attempt to restore content that never existed.

7.4 ehash_initialize_dir_new_page — stamping a fresh directory page

file_alloc_multiple invokes this callback once per newly allocated page, to mark the page type and, for persistent files, log the allocation.

// ehash_initialize_dir_new_page -- src/storage/extendible_hash.c
ehash_initialize_dir_new_page (THREAD_ENTRY * thread_p, PAGE_PTR page_p, void *args)
{
  bool is_temp = *(bool *) args;                 /* <- &is_temp forwarded through file_alloc_multiple */
  pgbuf_set_page_ptype (thread_p, page_p, PAGE_EHASH);
  if (!is_temp)                                  /* <- persistent: log the allocation, zero-length payloads */
    log_append_undoredo_data2 (thread_p, RVEH_INIT_NEW_DIR_PAGE, NULL, page_p, -1, 0, 0, NULL, NULL);
  pgbuf_set_dirty (thread_p, page_p, DONT_FREE);
  return NO_ERROR;
}

The RVEH_INIT_NEW_DIR_PAGE undoredo has NULL data on both sides; the redo handler ehash_rv_init_dir_new_page_redo only re-stamps PAGE_EHASH and dirties the page, while the empty undo side relies on file_alloc_multiple’s own deallocation undo. The is_temp == true path skips logging — temporary EHID files are never recovered (the !is_temp gate seen throughout). args is void * because file_alloc_multiple is generic; the callback casts it back to bool *.

7.5 ehash_connect_bucket — re-targeting a contiguous pointer run

This function sets every directory slot whose first local_depth bits match hash_key’s to bucket_vpid. With global depth d there are exactly 2^(d - local_depth) such slots, contiguous because they differ only in the low d - local_depth bits.

Computing the run. It fixes the header (read latch), memcpys it into dir_header, unfixes; a header-fix failure returns ER_FAILED before any mutation, so there is no sysop to unwind (unlike the in-loop write-latch failure below). It then computes location = GETBITS (hash_key, 1, dir_header.depth) (the d-bit directory index) and diff = dir_header.depth - local_depth.

// ehash_connect_bucket -- src/storage/extendible_hash.c
if (diff != 0)
  {
    for (set_bits = 0, i = 0; i < diff; i++)
      set_bits = 2 * set_bits + 1;                     /* <- low diff bits all 1 */
    clear_bits = ~set_bits;
    first_ptr_offset = location & clear_bits;          /* <- low diff bits forced to 0 */
    last_ptr_offset  = location | set_bits;            /* <- low diff bits forced to 1 */
    ehash_dir_locate (&first_page, &first_ptr_offset);  ehash_dir_locate (&last_page, &last_ptr_offset);
  }
else                                                   /* <- single pointer (local == global) */
  { first_ptr_offset = location; ehash_dir_locate (&first_page, &first_ptr_offset);
    last_page = first_page; last_ptr_offset = first_ptr_offset; }

The diff != 0 branch handles a multi-slot run: location & clear_bits is the first flat index, location | set_bits the last, each mapped by ehash_dir_locate to a (page, offset). The diff == 0 branch (local_depth == dir_header.depth) collapses to one slot. location is the flat slot index; ehash_dir_locate rewrites the byte *_ptr_offset values in place.

The per-page update loop fixes each page in [first_page, last_page] (write latch) and rewrites the in-range slots:

// ehash_connect_bucket (update loop) -- src/storage/extendible_hash.c
for (i = first_page; i <= last_page; i++)
  {
    page_p = ehash_fix_nth_page (..., i, PGBUF_LATCH_WRITE);
    if (page_p == NULL) return ER_FAILED;              /* <- in-loop fix failure: sysop will abort */
    start_offset = (i == first_page) ? first_ptr_offset : 0;
    end_offset   = (i == last_page)  ? last_ptr_offset + sizeof (EHASH_DIR_RECORD) : DB_PAGESIZE;
    bef_length = end_offset - start_offset;
    repetition.count = bef_length / sizeof (EHASH_DIR_RECORD);   /* <- run length on THIS page */
    if (!is_temp)                                                /* undo = bef_length pre-image bytes; redo = &repetition */
      log_append_undoredo_data2 (..., RVEH_CONNECT_BUCKET, ..., page_p, start_offset, bef_length,
                                 sizeof (EHASH_REPETITION), (char *) page_p + start_offset, &repetition);
    dir_record_p = (EHASH_DIR_RECORD *) ((char *) page_p + start_offset);
    for (j = 0; j < repetition.count; j++)
      { dir_record_p->bucket_vpid = *bucket_vpid_p; dir_record_p++; }   /* <- stamp target vpid */
    pgbuf_set_dirty (thread_p, page_p, FREE);
  }

The start_offset/end_offset ternaries clip the run to the page: it may start mid-page on first_page and end mid-page on last_page, otherwise spanning [0, DB_PAGESIZE). An in-loop fix failure returns ER_FAILED immediately; the caller’s log_sysop_abort (the sysop was opened with log_sysop_start in ehash_extend_bucket) rolls back the already-logged partial updates.

Invariant (one WAL record per page, redo payload O(1)): however many pointers a page’s run covers, exactly one RVEH_CONNECT_BUCKET record is emitted, its redo payload sizeof(EHASH_REPETITION) regardless of count. The undo side is not O(1) — literal pre-image bytes, since prior content can be an arbitrary mixture — but the redo side, the common replay path, is. What breaks if violated: per-slot logging would let a deep directory emit a proportional flood of records during one split, defeating the run-length design.

7.6 Stitching it together — the re-insert decision

After ehash_extend_bucket commits its sysop and returns the sibling page (or NULL on error, which unfixes the bucket and returns EHASH_ERROR_OCCURRED), ehash_insert_bucket_after_extend_if_need uses the out_new_bit captured in §7.1:

// ehash_insert_bucket_after_extend_if_need -- src/storage/extendible_hash.c
target_bucket_page_p = new_bit ? sibling_page_p : bucket_page_p;  /* <- MSB 1 -> sibling, 0 -> original */
result = ehash_insert_to_bucket (..., target_bucket_page_p, ...);

new_bit is the new_local_depth-th bit of the triggering key’s hash. The §7.1 connect calls made every bit-0 slot point at the original and every bit-1 slot at the sibling; this if mirrors that split for the overflow record. Because the bucket was just split, the chosen side has free space, so the re-insert does not recurse — the same condition Chapter 6’s separating-depth invariant guarantees.

7.7 Chapter summary — key takeaways

1. The doubling restores the standing depth-ceiling invariant local_depth <= global depth: a split that raises a bucket above global depth transiently breaks it, and ehash_expand_directory lifting depth to new_local_depth repairs it.
2. Two orthogonal gates fire after a split: new_local_depth > depth doubles the directory; (new_local_depth - old_local_depth) > 1 triggers the NULL-then-relink branch (Figure 7-1).
3. ehash_expand_directory doubles in place via a backward dual-cursor walk, so no source pointer is overwritten before it is read.
4. Reused directory pages carry RVEH_REPLACE undo pre-images; fresh pages rely on RVEH_INIT_NEW_DIR_PAGE plus the file manager’s allocation-undo.
5. EHASH_REPETITION {vpid, count} keeps connect redo O(1) per page and idempotent; the undo side carries literal pre-image bytes.
6. The connect run is contiguous and bit-derived: set_bits/clear_bits mask the low depth - local_depth bits of location for the first and last flat index.
7. The three connect calls — NULL the stale range, CLEARBIT the lower half to the original, SETBIT the upper half to the sibling — enforce the pointer-coverage invariant; out_new_bit, captured before any mutation, picks the re-insert side so the new free space absorbs the triggering key without a second split.

Chapter 8: Deleting a Key and Merging Buckets

Reader question: how is a key removed, and when does removing it merge two buckets back together? Deletion mirrors insertion (Ch 5-7) with one deliberate asymmetry: insertion can mutate the directory on the hot path, deletion never does. The common delete touches one bucket page, emits two log records, and returns; only when a bucket drops below an occupancy floor does the code descend a second time, under a stronger latch, into the merge machinery. This chapter traces every branch of ehash_delete, ehash_check_merge_possible, ehash_merge, ehash_merge_permanent, and ehash_find_depth. The shrink body (ehash_shrink_directory_if_need) is Chapter 9. No new structs (see Chapter 1 for the three headers).

8.1 The two-phase shape of a delete

ehash_delete runs entirely outside any system operation: it removes the record, logs it, and — only if the bucket is now starved — releases both latches and calls ehash_merge, which re-descends from scratch under PGBUF_LATCH_WRITE on the root. The phase boundary is the unfix between the delete and the merge re-descent; the merge owns root-WRITE from the start.

Why no S-to-X promotion path? Insert promotes the root latch READ->WRITE because a split mutates the directory. Delete’s hot path never mutates the directory, so the root stays PGBUF_LATCH_READ; all directory mutation lives in the second descent inside ehash_merge. Nothing to promote.

8.2 Descent, the not-found paths, and record removal

// ehash_delete -- src/storage/extendible_hash.c
dir_root_page_p = ehash_find_bucket_vpid_with_hash (thread_p, ehid_p, key_p, PGBUF_LATCH_READ,
                                    PGBUF_LATCH_WRITE, &bucket_vpid, NULL, &location);  /* root S, bucket X */
if (dir_root_page_p == NULL) return NULL;       /* <- descent failed, nothing fixed */
dir_header_p = (EHASH_DIR_HEADER *) dir_root_page_p;
if (bucket_vpid.pageid == NULL_PAGEID)          /* (1) directory slot points at no bucket */
  { pgbuf_unfix_and_init (thread_p, dir_root_page_p); er_set (..., ER_EH_UNKNOWN_KEY, 0); return NULL; }
bucket_page_p = ehash_fix_old_page (thread_p, &ehid_p->vfid, &bucket_vpid, PGBUF_LATCH_WRITE);
if (bucket_page_p == NULL) { pgbuf_unfix_and_init (thread_p, dir_root_page_p); return NULL; }
if (ehash_locate_slot (thread_p, bucket_page_p, dir_header_p->key_type, key_p, &slot_no) == false)
  { pgbuf_unfix_and_init (thread_p, bucket_page_p);   /* (2) key absent from a real bucket */
    pgbuf_unfix_and_init (thread_p, dir_root_page_p); er_set (..., ER_EH_UNKNOWN_KEY, 0); return NULL; }

The descent (Chapter 3) requests READ on the root, WRITE on the bucket. There are two distinct not-found paths, both raising ER_EH_UNKNOWN_KEY as a warning: (1) an empty directory slot (bucket_vpid.pageid == NULL_PAGEID) — the entry never pointed at a bucket, e.g. a slot reset by a prior merge (8.7), root unfixed; (2) the key absent from a fixed bucket (ehash_locate_slot == false), both pages unfixed. When the slot is found, the record is peeked and both log descriptors are built before the record is destroyed, because spage_delete invalidates the peeked pointer.

8.3 RVEH_DELETE: logical undo, physical redo

The undo and redo descriptors for the same RVEH_DELETE index carry different payloads — the heart of crash-recoverable extendible hashing.

// ehash_delete -- src/storage/extendible_hash.c
(void) spage_get_record (thread_p, bucket_page_p, slot_no, &bucket_recdes, PEEK);
/* undo recdes = EHID || (value, key) -- file id, NOT page/slot;  redo recdes = type(short) || (value, key) */
(void) spage_delete (thread_p, bucket_page_p, slot_no);     /* <- record gone */
pgbuf_set_dirty (thread_p, bucket_page_p, DONT_FREE);
if (!is_temp)
  { log_append_undo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, NULL, ...);            /* NULL page = logical */
    log_append_redo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, bucket_page_p, slot_no, ...); } /* physical */

Invariant (logical undo must survive a later split). The undo record carries EHID || (value, key) attached to the file (page == NULL), forcing recovery down the logical undo handler (inverse re-insert), not a physical page patch. A physical (page, slot) undo would, after a concurrent split between delete and rollback, re-insert into a slot now owned by a different bucket. Logical undo re-hashes the key and re-locates the correct bucket regardless of intervening directory changes.

The redo record is purely physical (bucket_page_p, slot_no), replayed forward from a known page image, carrying type || (value, key) to rebuild the record byte-for-byte. The #if defined (ENABLE_UNUSED_FUNCTION) overflow-VPID block for REC_BIGONE long strings is compiled out (is_long_str stays false, overflow_delete unreached). is_temp (from file_is_temp) gates all logging — a temp hash deletes with no WAL traffic.

8.4 The underflow test and why 0.4-vs-0.9

After spage_delete, occupancy is classified into exactly one of three results:

// ehash_delete -- src/storage/extendible_hash.c
if (spage_number_of_records (bucket_page_p) <= 1)          /* slot 0 is the header -> logically empty */
  result = EHASH_BUCKET_EMPTY;
else if ((DB_PAGESIZE - spage_max_space_for_new_record (thread_p, bucket_page_p)) < EHASH_UNDERFLOW_THRESHOLD)
  result = EHASH_BUCKET_UNDERFLOW;                          /* used < 0.4 * PAGESIZE */
else
  result = EHASH_SUCCESSFUL_COMPLETION;                     /* healthy, no merge attempt */

<= 1 records means only the header slot remains; otherwise DB_PAGESIZE - max_space is the bytes in use. The thresholds are EHASH_UNDERFLOW_RATE 0.4 and EHASH_OVERFLOW_RATE 0.9, each times DB_PAGESIZE (-> EHASH_UNDERFLOW_THRESHOLD / EHASH_OVERFLOW_THRESHOLD).

Invariant (hysteresis prevents split-merge yo-yo). A merge is considered only below 0.4, but allowed only if both buckets combined stay at or below 0.9 (checked in 8.6); the two distinct rates enforce the gap. Were floor and ceiling equal, a bucket on the line would merge, overflow, split on the next insert, fall below, merge again — thrashing every operation. The 0.4/0.9 gap lands a merged bucket mid-range.

On EHASH_SUCCESSFUL_COMPLETION the bucket is healthy: skip the probe, unfix both pages, return key_p.

8.5 The S_LOCK probe and the latch handoff

When empty or underflown, ehash_delete runs a read-only S_LOCK probe of ehash_check_merge_possible, then drops both latches — it never merges while holding them:

// ehash_delete -- src/storage/extendible_hash.c
do_merge = false;
if (result == EHASH_BUCKET_EMPTY || result == EHASH_BUCKET_UNDERFLOW)
  if (ehash_check_merge_possible (thread_p, ehid_p, dir_header_p, &bucket_vpid, bucket_page_p, location,
                                  S_LOCK, &old_local_depth, &sibling_vpid, NULL, NULL, NULL, NULL)
      == EHASH_SUCCESSFUL_COMPLETION)
    do_merge = true;
pgbuf_unfix_and_init (thread_p, bucket_page_p);     /* <- release BEFORE merge */
pgbuf_unfix_and_init (thread_p, dir_root_page_p);
if (do_merge) ehash_merge (thread_p, ehid_p, key_p, is_temp);   /* re-descends from scratch */
return (key_p);

The probe is purely advisory: both pages release before ehash_merge runs, so a concurrent transaction may refill the bucket. It only skips a wasted second descent when there is obviously no sibling; ehash_merge re-validates everything (8.7).

8.6 ehash_check_merge_possible: the three return codes

Two modes via lock_type (S_LOCK = probe, X_LOCK = commit). The sibling slot differs from location only in the bit at position local_depth (from the most significant key bit); branch (D) rejects a differing-depth sibling because buckets are true buddies only at equal local_depth. The space test runs only when num_records > 1; in X_LOCK mode the sibling stays write-fixed and is handed to the merge, in S_LOCK it is always unfixed.

// ehash_check_merge_possible -- src/storage/extendible_hash.c
*out_old_local_depth_p = bucket_header_p->local_depth;
if (bucket_header_p->local_depth == 0) return EHASH_NO_SIBLING_BUCKET;  /* (A) lone depth-0 bucket */
ehash_find_bucket_vpid (..., loc, PGBUF_LATCH_READ, sibling_vpid_p);    /* loc = location with local_depth bit flipped */
if (VPID_ISNULL (sibling_vpid_p))            return EHASH_NO_SIBLING_BUCKET;  /* (B) slot empty */
if (VPID_EQ (sibling_vpid_p, bucket_vpid_p)) return EHASH_NO_SIBLING_BUCKET;  /* (C) self       */
sibling_page_p = ehash_fix_old_page (..., lock_type == S_LOCK ? PGBUF_LATCH_READ : PGBUF_LATCH_WRITE);
spage_next_record (sibling_page_p, &first_slot_id, &recdes, COPY);            /* sibling header */
if (sibling_bucket_header.local_depth != bucket_header_p->local_depth)
  { pgbuf_unfix_and_init (thread_p, sibling_page_p); return EHASH_NO_SIBLING_BUCKET; }  /* (D) depth mismatch */
if (spage_number_of_records (bucket_page_p) > 1)         /* space test only when source has records to move */
  if ((sibling_used + bytes_to_transfer) > EHASH_OVERFLOW_THRESHOLD)                /* > 0.9 */
    { pgbuf_unfix_and_init (thread_p, sibling_page_p); return EHASH_FULL_SIBLING_BUCKET; }
if (lock_type == S_LOCK) pgbuf_unfix_and_init (thread_p, sibling_page_p);  /* probe: release */
else *out_sibling_page_p = sibling_page_p;  /* commit: keep WRITE-fixed, + first_slot_id, num_records, loc */
return EHASH_SUCCESSFUL_COMPLETION;

Return code	When	Caller (ehash_merge) does
EHASH_NO_SIBLING_BUCKET	depth 0 (A), empty slot (B), self (C), depth mismatch (D)	empty-bucket special case (8.7) or nothing
EHASH_FULL_SIBLING_BUCKET	sibling + transfer > 0.9	unfix bucket, do not merge
EHASH_SUCCESSFUL_COMPLETION	buddy found, records fit	run ehash_merge_permanent
EHASH_ERROR_OCCURRED	fix/scan failure	unfix all, return

8.7 ehash_merge: re-descent, re-validation, and the branch switch

ehash_merge is the committing pass: re-descend root-WRITE, re-fix the bucket WRITE, then recompute the same three-way classification as 8.4 — BUCKET_EMPTY / BUCKET_UNDERFLOW / refilled (bucket_status = NO_ERROR).

Invariant (re-validation against concurrent refill). A concurrent insert may have refilled the bucket above the floor while the probe held no latches. Recomputing bucket_status and unfixing on NO_ERROR keeps the merge from proceeding on a now-healthy bucket (which would overflow the sibling or strand records). On NO_ERROR the whole if is bypassed and control falls to the final pgbuf_unfix_and_init (dir_root_page_p).

If still empty/underflown, ehash_check_merge_possible is called with X_LOCK, leaving the sibling write-latched. The result drives a five-way switch (Figure 8-1):

flowchart TD
  A["re-fix root X, bucket X"] --> B{"still empty/underflow?"}
  B -- "no, refilled" --> Z["unfix root, return"]
  B -- yes --> C["check_merge_possible X_LOCK"]
  C --> D{"result"}
  D -- NO_SIBLING --> E{"EMPTY and depth != 0?"}
  E -- yes --> F["sysop: dealloc + connect NULL_VPID\nadjust old -1, shrink?, commit"]
  E -- no --> G["unfix bucket"]
  D -- FULL_SIBLING --> H["unfix bucket, no merge"]
  D -- SUCCESSFUL --> I["sysop: merge_permanent + dealloc\nadjust old -2, new +1, shrink?\nconnect sibling, commit"]
  D -- ERROR --> J["unfix bucket + root, return"]
  D -- default --> K["ER_EH_CORRUPTED, unfix"]
  F --> Z
  G --> Z
  H --> Z
  I --> Z

Figure 8-1. ehash_merge switch. Every arm except SUCCESSFUL and the empty-bucket sub-case ends without mutating the directory.

EHASH_NO_SIBLING_BUCKET — no buddy. If the bucket is empty with old_local_depth != 0, its page is pure waste and is reclaimed under a system operation; any failure triggers log_sysop_abort:

// ehash_merge -- src/storage/extendible_hash.c  (NO_SIBLING_BUCKET arm)
pgbuf_unfix_and_init (thread_p, bucket_page_p);
if ((bucket_status == EHASH_BUCKET_EMPTY) && (old_local_depth != 0))
  { if (!is_temp) log_sysop_start (thread_p);
    if (file_dealloc (..., &bucket_vpid, FILE_EXTENDIBLE_HASH) != NO_ERROR) { /* abort, return */ }
    if (ehash_connect_bucket (..., old_local_depth, hash_key, &null_vpid, is_temp) != NO_ERROR) { /* abort */ }
    ehash_adjust_local_depth (..., old_local_depth, -1, is_temp);   /* one bucket gone */
    ehash_shrink_directory_if_need (thread_p, ehid_p, dir_header_p, is_temp);
    if (!is_temp) log_sysop_commit (thread_p); }

When old_local_depth == 0 this is the single global bucket; it is kept even when empty — there must always be one bucket — and simply unfixed. EHASH_FULL_SIBLING_BUCKET — buddy too full; the record is already deleted, so the bucket is just released (no merge, no sysop). EHASH_SUCCESSFUL_COMPLETION — the real merge (8.8). EHASH_ERROR_OCCURRED unfixes bucket+root and returns. default is unreachable; it raises ER_EH_CORRUPTED.

8.8 ehash_merge_permanent and the two adjust calls

ehash_merge_permanent moves the source records into the still-fixed sibling, recomputes its local depth, and rewrites the sibling header — bracketing the mutation with a full-page RVEH_REPLACE undo/redo image so recovery restores or replays the merged page atomically.

// ehash_merge_permanent -- src/storage/extendible_hash.c
if (!is_temp)  /* full-page undo image; symmetric redo emitted after the loop */
  log_append_undo_data2 (thread_p, RVEH_REPLACE, &ehid_p->vfid, sibling_page_p, 0, DB_PAGESIZE, sibling_page_p);
for (slot_id = 1; slot_id < num_records; slot_id++)        /* skip header slot 0 */
  { spage_get_record (thread_p, bucket_page_p, slot_id, &recdes, PEEK);
    bucket_record_p = (char *) recdes.data + sizeof (OID);            /* skip assoc-value, point at key */
    is_record_exist = ehash_locate_slot (..., (void *) bucket_record_p, &new_slot_id);
    if (is_record_exist == false)                                    /* re-insert in sort order */
      { if (spage_insert_at (thread_p, sibling_page_p, new_slot_id, &recdes) != SP_SUCCESS) return ER_FAILED; }
    else { er_set (..., ER_EH_CORRUPTED, 0); return ER_FAILED; } }    /* dup key = corruption */
found_depth = ehash_find_depth (thread_p, ehid_p, location, bucket_vpid_p, sibling_vpid_p);
if (found_depth == 0) return ER_FAILED;
sibling_bucket_header.local_depth = dir_header_p->depth - found_depth;   /* recomputed; then spage_update + set_dirty */
*out_new_local_depth_p = sibling_bucket_header.local_depth;

A key already present in the sibling (is_record_exist == true) is ER_EH_CORRUPTED — buddies hold disjoint key sets. Back in ehash_merge’s SUCCESSFUL arm the source is deallocated and the directory bookkeeping fixed up:

// ehash_merge -- src/storage/extendible_hash.c  (SUCCESSFUL arm)
file_dealloc (thread_p, &dir_header_p->bucket_file, &bucket_vpid, FILE_EXTENDIBLE_HASH);
ehash_adjust_local_depth (..., old_local_depth, -2, is_temp);
ehash_adjust_local_depth (..., new_local_depth, 1, is_temp);
ehash_shrink_directory_if_need (thread_p, ehid_p, dir_header_p, is_temp);
ehash_connect_bucket (..., new_local_depth, hash_key, &sibling_vpid, is_temp);

Invariant (local_depth_count conservation). Merging two depth-d buddies into one depth-d-1 bucket means -2 at d, +1 at d-1. The two ehash_adjust_local_depth calls enforce it: (old_local_depth, -2) removes both pre-merge buckets, (new_local_depth, +1) adds the merged one. A miscount triggers a spurious shrink (orphaning entries) or blocks a needed one (leaking pages), since Chapter 9 reads this counter top-down. The empty-bucket sub-case (8.7) is the degenerate version: one bucket vanishes with no target — a single (old_local_depth, -1).

ehash_find_depth recomputes new_local_depth instead of assuming old_local_depth - 1: it widens check_depth over the directory neighborhood around location while every probed entry points at the source, the sibling, or NULL, stopping at the first foreign entry — so depth - found_depth can be less than old_local_depth - 1 when adjacent slots already collapsed to NULL. ehash_connect_bucket (Chapter 7) then points every entry in the merged region at sibling_vpid (null_vpid in the empty case); ehash_shrink_directory_if_need runs in the same sysop (Chapter 9).

8.9 Chapter summary — key takeaways

1. Delete is two-phase by design. ehash_delete removes and logs under root-S/bucket-X, never mutating the directory; a starved bucket releases both latches and calls ehash_merge, which re-descends under root-X. No S-to-X promotion because the hot path is directory-read-only.
2. RVEH_DELETE is logical-undo, physical-redo. Undo (EHID || value || key, NULL page) re-hashes on rollback and survives an intervening split; redo (type || value || key at fixed page+slot) replays forward. is_temp suppresses all logging.
3. 0.4 floor, 0.9 ceiling, on purpose. EHASH_UNDERFLOW_THRESHOLD decides whether to attempt a merge; EHASH_OVERFLOW_THRESHOLD (in 8.6) decides whether it fits. The gap is hysteresis against split-merge thrashing, re-validated by ehash_merge after the advisory probe drops all latches.
4. ehash_check_merge_possible returns three codes. NO_SIBLING_BUCKET (depth 0 / empty slot / self / depth mismatch), FULL_SIBLING_BUCKET (> 0.9), SUCCESSFUL_COMPLETION (buddy fits); in X_LOCK mode it leaves the sibling write-latched for the merge.
5. The real merge moves records, recomputes depth, rewires, re-counts. ehash_merge_permanent re-inserts every source record into the sibling (a duplicate is ER_EH_CORRUPTED) under a full-page RVEH_REPLACE image and recomputes depth via ehash_find_depth; ehash_merge then deallocates the source and issues adjust_local_depth(old, -2) + (new, +1), conserving local_depth_count. The empty-bucket-with-local_depth != 0 case is the degenerate merge: dealloc, entries reset to NULL_VPID, count -1, one log_sysop bracket — the lone depth-0 bucket is always kept.

Chapter 9: Shrinking the Directory

The reader question: after merges have lowered bucket local depths, when and how does the global depth come back down? Chapter 8 traced how ehash_merge collapses a bucket pair and adjusts the local-depth histogram. This chapter follows the other half: the histogram-driven decision to contract the directory (ehash_shrink_directory_if_need) and the physical halving (ehash_shrink_directory). Shrink mirrors the doubling in Chapter 7 — read that chapter for the directory-page layout and ehash_dir_locate, and the companion cubrid-extendible-hash.md for why the directory shrinks lazily.

No new structs are introduced. The single field that drives everything is EHASH_DIR_HEADER::local_depth_count, maintained by ehash_adjust_local_depth (Chapters 6 and 8):

// struct ehash_dir_header -- src/storage/extendible_hash.c
  int local_depth_count[EHASH_HASH_KEY_BITS + 1];   /* histogram: index == local depth */
  short depth;                  /* global depth of the directory: 2^depth pointers */

local_depth_count[d] counts buckets whose local depth equals d; depth is the global depth. The histogram lets a delete-time merge decide, in O(depth) integer reads and without walking every bucket, whether the directory has grown too tall for the buckets it now serves.

9.1 The histogram invariant that makes shrink safe

INVARIANT (histogram completeness). For every level d, local_depth_count[d] equals the number of buckets whose local depth is exactly d; equivalently the highest d with a non-zero count never exceeds dir_header->depth. If a merge dropped one of its deltas, the highest non-zero level scanned below would lie about the tallest bucket, and ehash_shrink_directory could lower depth beneath a live bucket’s local depth — orphaning its sibling pointers and corrupting lookups.

This is enforced by routing every local-depth change through ehash_adjust_local_depth, the only writer of the histogram, which logs an RVEH_INC_COUNTER undo/redo so recovery reconstructs the same counts:

// ehash_adjust_local_depth -- src/storage/extendible_hash.c
  dir_header_p->local_depth_count[depth] += delta;          /* <- the only writer of the histogram */
  redo_inc = delta;
  undo_inc = -delta;                                        /* <- undo simply negates the increment */
  if (!is_temp)
    log_append_undoredo_data2 (thread_p, RVEH_INC_COUNTER, ... &undo_inc, &redo_inc);

The deltas come in matched pairs at the two merge call sites (Chapter 8): the empty-bucket path passes (old_local_depth, -1); the record-move path turns two buckets at old_local_depth into one at new_local_depth = old_local_depth - 1 via (old_local_depth, -2) then (new_local_depth, +1). Either way the population at the tallest levels drops — the signal shrink watches for.

Figure 9-1 shows the relationship the invariant ties together:

flowchart LR
  subgraph H["dir_header (root page 0)"]
    D["depth = global depth"]
    LDC["local_depth_count[0..KEY_BITS]"]
  end
  ALD["ehash_adjust_local_depth\nthe only writer"] -->|"+/- delta + RVEH_INC_COUNTER log"| LDC
  MERGE["ehash_merge paths\n(Chapter 8)"] --> ALD
  LDC -->|"scanned downward"| IFNEED["ehash_shrink_directory_if_need"]
  D -->|"start of scan"| IFNEED
  IFNEED -->|"if 2+ idle levels"| SHRINK["ehash_shrink_directory"]
  SHRINK -->|"writes new depth"| D

9.2 ehash_shrink_directory_if_need — the contraction trigger

Called from inside the merge system operation, after this merge’s histogram deltas are applied. It reads the histogram top-down to decide whether a physical shrink is worthwhile:

// ehash_shrink_directory_if_need -- src/storage/extendible_hash.c
  int i;
  i = dir_header_p->depth;
  while (dir_header_p->local_depth_count[i] == 0)   /* <- walk down past every empty top level */
    {
      i--;
    }
  if ((dir_header_p->depth - i) > 1)                /* <- need at least two idle levels */
    {
      ehash_shrink_directory (thread_p, ehid_p, i + 1, is_temp);
    }

Branch-complete walkthrough:

1. i = dir_header_p->depth — start at the top, the level no bucket may exceed.
2. while (local_depth_count[i] == 0) i-- — descend while the level holds no buckets. Because local_depth_count[0] is seeded to 1 in ehash_create_helper and never empties, the loop is bounded and lands on the highest level holding a bucket, i.
   • Loop never runs (local_depth_count[depth] != 0) — a bucket already sits at the global depth, i == depth, nothing idle.
   • Loop runs k times — the top k levels are empty; the tallest surviving bucket has local depth i = depth - k.
3. if ((depth - i) > 1) — depth - i is the number of fully idle top levels; shrink fires only when that is strictly greater than 1. 0 and 1 idle levels are both skipped (the latter is the hysteresis band); >= 2 shrinks, requesting new_depth = i + 1 to keep one idle level as headroom rather than going to i. Even with three idle levels this is a single call — ehash_shrink_directory computes times from the depth gap and never recurses.

INVARIANT (anti-oscillation hysteresis). The directory shrinks only when at least two depth levels are idle ((depth - i) > 1) and shrinks to i + 1, leaving one idle level. Doubling (Chapter 7) fires the instant a single bucket needs new_local_depth > depth — a > 0-style trigger. If shrink fired on the symmetric single-idle-level condition, one delete vacating the top level would shrink, and the next insert re-splitting a bucket to that depth would immediately re-double: an O(directory-size) memcpy on every alternating insert/delete at the boundary. Demanding two idle levels and stopping one short lets the structure absorb a full level of churn before paying for either move. What breaks if violated: a > 0 test makes the directory a memcpy treadmill on workloads oscillating around a power-of-two bucket count — correctness survives, throughput does not.

9.3 ehash_shrink_directory — physically halving the array

The structural mirror of ehash_expand_directory (Chapter 7). Doubling fanned each old pointer into a times-fold range right-to-left; shrinking samples every times-th old pointer into a packed range left-to-right, since the destination always trails the source. Figure 9-2 traces it; labels (A)–(D) match the copy-loop excerpt.

flowchart TD
  A0{"fix page 0 ok?"} -->|no| A0r["return (nothing held)"]
  A0 -->|yes| B{"depth < new_depth?"}
  B -->|yes| Babort["WARNING, unfix page 0, return"]
  B -->|no| C["compute old_ptrs, times, new_ptrs\nlog RVEH_REPLACE undo of page 0\ndir_header->depth = new_depth"]
  C --> F["loop i = 1 .. new_ptrs-1"]
  F --> H{"source page changed? (A)"}
  H -->|yes| H2["unfix old, fix next source page"]
  H -->|no| J
  H2 --> J{"dest page full? (B)"}
  J -->|yes| J2["redo full dest page, fix next dest\nnew_dir_offset = 0, undo new page (C)"]
  J -->|no| K
  J2 --> K["memcpy one EHASH_DIR_RECORD (D)"]
  K --> F
  F -->|done| M["redo last dest page\nfile_numerable_truncate to new_pages+1"]

Setup, early-return, header logging. Fix root page 0, guard against a stale request, compute the geometry, log the page-0 undo image, write the new depth:

// ehash_shrink_directory -- src/storage/extendible_hash.c
  dir_header_p = (EHASH_DIR_HEADER *) ehash_fix_nth_page (thread_p, &ehid_p->vfid, 0, PGBUF_LATCH_WRITE);
  if (dir_header_p == NULL)
    {
      return;                              /* <- page-0 fix failed; abort shrink, nothing fixed to release */
    }
  if (dir_header_p->depth < new_depth)
    {
      pgbuf_unfix (thread_p, (PAGE_PTR) dir_header_p);
      return;                              /* <- requested depth larger than current; nothing to do */
    }
  old_ptrs = 1 << dir_header_p->depth;
  times = 1 << (dir_header_p->depth - new_depth);   /* <- stride: old slots collapsed into one */
  ret = file_get_num_user_pages (thread_p, &ehid_p->vfid, &old_pages);
  // ... condensed: on error, ASSERT_ERROR + unfix + return ...
  new_ptrs = old_ptrs / times;             /* <- pointer count after the shrink */
  new_dir_page_p = (PAGE_PTR) dir_header_p;   /* <- destination starts ON the header page */
  new_dir_offset = EHASH_DIR_HEADER_SIZE;  /* first pointer sits right after the header */
  if (!is_temp)                            /* <- full-page UNDO of page 0 before any write */
    log_append_undo_data2 (thread_p, RVEH_REPLACE, ... new_dir_page_p ...);
  dir_header_p->depth = new_depth;         /* <- global depth decreases here, under the page-0 X latch */

times = 2^(old_depth - new_depth); because the caller always requests new_depth = i + 1, times >= 2 whenever shrink runs. Source and destination cursors both start at page 0 — the surviving prefix is packed back over the front of the same array, so they coexist on the first page; pointer 0 never moves and the loop starts at i = 1. There are exactly three pre-loop exits, and they differ in what is held when control returns: (1) page-0 fix failure (ehash_fix_nth_page returns NULL) — the very first early exit, taken before any page is pinned, so it just returns with nothing to release; (2) stale request (dir_header_p->depth < new_depth) — page 0 is already pinned, so it pgbuf_unfixes page 0 and returns; (3) file_get_num_user_pages error — ASSERT_ERROR (), then unfix page 0 and return. Past these three guards the function is committed to the copy loop.

The copy loop — every branch. For each surviving pointer i from 1 to new_ptrs - 1:

// ehash_shrink_directory -- src/storage/extendible_hash.c
  for (i = 1; i < new_ptrs; i++)
    {
      old_dir_offset = i * times;                       /* <- sample every times-th old pointer */
      ehash_dir_locate (&old_dir_nth_page, &old_dir_offset);
      if (old_dir_nth_page != prev_pg_no)               /* (A) source crossed a page boundary */
        {
          prev_pg_no = old_dir_nth_page;
          pgbuf_unfix_and_init (thread_p, old_dir_page_p);
          old_dir_page_p = ehash_fix_nth_page (thread_p, &ehid_p->vfid, old_dir_nth_page, PGBUF_LATCH_WRITE);
          // ... condensed: NULL -> set_dirty(new) FREE + return ...
        }
      new_dir_offset += sizeof (EHASH_DIR_RECORD);
      if ((DB_PAGESIZE - new_dir_offset) < SSIZEOF (EHASH_DIR_RECORD))   /* (B) dest page full */
        {
          if (!is_temp)                                 /* finalize filled dest page: full-page REDO */
            log_append_redo_data2 (thread_p, RVEH_REPLACE, ... new_dir_page_p ...);
          pgbuf_set_dirty (thread_p, new_dir_page_p, FREE);
          new_dir_nth_page++;
          new_dir_page_p = ehash_fix_nth_page (thread_p, &ehid_p->vfid, new_dir_nth_page, PGBUF_LATCH_WRITE);
          // ... condensed: NULL -> unfix(old) + return ...
          new_dir_offset = 0;
          if (!is_temp)                                 /* (C) capture this page's pre-image: full-page UNDO */
            log_append_undo_data2 (thread_p, RVEH_REPLACE, ... new_dir_page_p ...);
        }
      memcpy ((char *) new_dir_page_p + new_dir_offset, (char *) old_dir_page_p + old_dir_offset,
              sizeof (EHASH_DIR_RECORD));               /* (D) copy the sampled pointer down */
    }

• (A) source page boundary. i * times indexes the source in flattened pointer units; ehash_dir_locate converts it to (page, offset). On a page change the loop unfixes the current source page and fixes the next; because times >= 2, source pages are visited in strictly increasing order, each fixed once. A fix failure marks the destination dirty (FREE) and returns, leaving recovery to undo from the pre-images.
• (B) destination page full. The destination grows one EHASH_DIR_RECORD per iteration; when the next record will not fit, the completed page is logged RVEH_REPLACE redo (final image), dirty-and-freed, and the next page is fixed with new_dir_offset = 0.
• (C) new destination page undo. Right after fixing a fresh destination page (inside branch B), its pre-image is logged RVEH_REPLACE undo — one undo and one redo per modified page. Because shrink reuses the directory’s front pages, that page still holds discarded pointers; the pre-image lets recovery restore the larger directory on abort. (Page 0’s undo was logged before the loop.)
• (D) copy. A raw memcpy of one EHASH_DIR_RECORD (a VPID) from the sampled source to the packed destination — no interpretation, because surviving slots already point at the correct buckets. Shrinking changes which entries survive, never where a bucket lives.

Loop exit and trailing-page reclaim. The final (partially filled) destination page is logged redo and flushed, then trailing pages are truncated:

// ehash_shrink_directory -- src/storage/extendible_hash.c
  pgbuf_set_dirty (thread_p, new_dir_page_p, FREE);
  new_end_offset = new_ptrs - 1;
  ehash_dir_locate (&new_pages, &new_end_offset);        /* <- page holding the last surviving pointer */
  ret = file_numerable_truncate (thread_p, &ehid_p->vfid, new_pages + 1);   /* <- free trailing pages */
  // ... condensed: on error, ASSERT_ERROR only (best-effort) ...

ehash_dir_locate(new_ptrs - 1) computes new_pages, and the file is truncated to new_pages + 1 numerable pages — releasing every trailing old directory page in a single file_numerable_truncate, not a per-page file_dealloc loop (file_dealloc is what Chapter 8 uses for bucket pages). A truncation error is asserted but not propagated: the directory is already logically correct, so failing to reclaim disk is best-effort cleanup, not a transactional failure.

9.4 Keeping the histogram consistent for the next decision

ehash_shrink_directory writes dir_header_p->depth = new_depth but never touches local_depth_count — correctly, since contracting the array changes how many pointers exist, not how many buckets sit at each local depth, and the histogram already reflects post-merge reality (ehash_adjust_local_depth ran before the trigger at both call sites). After shrink the highest non-zero level is still i = new_depth - 1, so the 9.1 invariant holds with new_depth itself as the one idle headroom level: the next trigger scans from new_depth, skips it, lands on i = new_depth - 1, computes new_depth - i == 1 (not > 1), and declines to shrink again — settled, as the hysteresis intends, while a future split back up to new_depth is absorbed without doubling. Only ehash_adjust_local_depth writes the histogram (Chapters 6, 8); shrink and grow are pure readers of it, plus the scalar depth write.

9.5 Chapter summary — key takeaways

1. The histogram is the trigger, depth is the lever. ehash_shrink_directory_if_need scans local_depth_count down from dir_header->depth to the highest non-zero level i; only ehash_shrink_directory ever lowers the scalar dir_header->depth.
2. Two idle levels are required, one is kept. (depth - i) > 1 demands two empty top levels before shrinking, and shrink targets i + 1 so one idle level survives — the anti-oscillation hysteresis against the grow trigger; a > 0 test would reintroduce thrashing.
3. Shrink is structural doubling run backward. times = 2^(depth - new_depth), new_ptrs = old_ptrs / times, and the loop samples every times-th old pointer left-to-right, packing survivors over the front of the same file — the inverse of Chapter 7’s fan-out.
4. Every modified directory page is logged pre-image (undo) and post-image (redo) via RVEH_REPLACE, header undo and depth write done up front; trailing pages are reclaimed by one file_numerable_truncate(new_pages + 1) (not file_dealloc), best-effort.
5. Shrink never writes the histogram. It changes pointer counts, not bucket local depths, so local_depth_count stays as the preceding merge deltas set it — keeping the next decision correct (it sees new_depth - i == 1 and declines).
6. Correctness rests on the 9.1 completeness invariant. Every local-depth change funnels through ehash_adjust_local_depth (logged RVEH_INC_COUNTER), so the histogram is a crash-durable census; a missing delta would let shrink lower depth below a live bucket’s local depth and corrupt lookups.

Chapter 10: Edge Paths Recovery and Concurrency

This chapter gathers everything outside the insert-search-delete lifecycle (Chapters 5-9) plus crash recovery and concurrency. What happens when a directory slot points nowhere, how is the structure rebuilt after a crash, and what holds when two transactions touch the same hash at once? We assume the companion’s recovery model (cubrid-extendible-hash.md, “Crash Safety” / “Concurrency”) and do not re-derive WAL theory. The RV_fun[] dispatch machinery itself — how LOG_RCVINDEX selects an undo/redo function during the analysis/redo/undo passes — lives in cubrid-recovery-manager-detail.md; this chapter only covers the extendible-hash rows of that table.

10.1 Bucket creation when a directory slot is NULL_VPID

A freshly doubled directory (Chapter 7) leaves most new slots at NULL_VPID. The first insert resolving to such a slot lands in ehash_insert_helper’s VPID_ISNULL (&bucket_vpid) branch. Under S it cannot allocate, so it drops the latch and recurses with X_LOCK; under X it calls ehash_insert_to_bucket_after_create.

// ehash_insert_to_bucket_after_create -- src/storage/extendible_hash.c
found_depth = ehash_find_depth (thread_p, ehid_p, location, &null_vpid, &null_vpid);
if (found_depth == 0) { return ER_FAILED; }          /* <- find_depth signals error with 0 */
init_bucket_data[1] = dir_header_p->depth - found_depth;   /* <- new bucket's local depth */
log_sysop_start (thread_p);                           /* <- atomic allocate+connect+adjust */
error_code = file_alloc (..., ehash_initialize_bucket_new_page, init_bucket_data, bucket_vpid_p, &bucket_page_p);

ehash_find_depth picks the new bucket’s local depth covering exactly the contiguous slot run sharing its hash prefix. It walks outward from location (check_depth = 2, examining 2^(check_depth-2) siblings), accepting a slot only if VPID_ISNULL, VPID_EQ (bucket_vpid_p), or VPID_EQ (sibling_vpid_p); otherwise it breaks and returns check_depth - 1. On the create path both VPID args are &null_vpid, so only NULL slots qualify. Local depth is dir_header->depth - found_depth: deeper empty run → wider slot run.

file_alloc runs ehash_initialize_bucket_new_page (emitting RVEH_INIT_BUCKET, 10.2); ehash_connect_bucket writes the new VPID into all 2^(depth - local_depth) matching slots (Chapter 7); ehash_adjust_local_depth(..., +1, ...) bumps the per-depth counter; then the system op commits. Figure 10-1 traces the rest: connect failure → log_sysop_abort + ER_FAILED; success → log_sysop_commit then ehash_insert_to_bucket (a separate undo unit).

Invariant — the empty bucket is structurally complete before any key enters it. The allocate → connect → adjust-depth triple runs inside one system op committed before the first record write. A crash either rolls the structural op fully back (no bucket, slots still NULL — the next insert recreates it) or keeps it whole. Violate the ordering and a crash could leave a bucket whose local depth disagrees with its slot run, or an orphaned row in an unreferenced page.

The trailing if (ins_result != EHASH_SUCCESSFUL_COMPLETION) is a should-never-happen guard: a record short enough to be a fresh page’s first entry cannot be refused by the slotted-page layer, so it escalates to ER_FATAL_ERROR_SEVERITY.

flowchart TD
  A["VPID_ISNULL(bucket) under X"] --> B["ehash_find_depth\nlocation, null, null"]
  B -->|returns 0| C["return ER_FAILED"]
  B -->|returns d| D["log_sysop_start"]
  D --> E["file_alloc + init page"]
  E -->|err| F["log_sysop_abort; ER_FAILED"]
  E -->|page NULL| G["assert_release(false); abort; ER_FAILED"]
  E -->|ok| H["ehash_connect_bucket over run"]
  H -->|err| I["unfix; log_sysop_abort; ER_FAILED"]
  H -->|ok| J["adjust_local_depth(+1)"]
  J --> K["log_sysop_commit"]
  K --> L["ehash_insert_to_bucket"]
  L -->|not SUCCESS| M["FATAL er_set; unfix; ER_FAILED"]
  L -->|SUCCESS| N["unfix; NO_ERROR"]

Figure 10-1. ehash_insert_to_bucket_after_create — every branch.

10.2 The recovery handler set: redo/undo split

Recovery dispatch is the RV_fun[] table in recovery.c, indexed by LOG_RCVINDEX, binding each index to undo and redo functions; the table-walk during recovery is documented in cubrid-recovery-manager-detail.md. The extendible-hash rows are contiguous (RVEH_*, indices 58-65 in recovery.h: RVEH_REPLACE = 58 through RVEH_INIT_NEW_DIR_PAGE = 65). All eight belong to this module — RVEH_REPLACE is not an outsider: it is the whole-page before-image logger used by the split and the directory-double paths (10.5).

// RV_fun[] -- src/transaction/recovery.c
{RVEH_REPLACE, "RVEH_REPLACE", log_rv_copy_char, log_rv_copy_char, NULL, NULL},
{RVEH_INSERT, "RVEH_INSERT", ehash_rv_insert_undo, ehash_rv_insert_redo, NULL, NULL},
{RVEH_DELETE, "RVEH_DELETE", ehash_rv_delete_undo, ehash_rv_delete_redo, NULL, NULL},
/* ... RVEH_INIT_BUCKET, RVEH_CONNECT_BUCKET, RVEH_INC_COUNTER, RVEH_INIT_DIR, RVEH_INIT_NEW_DIR_PAGE ... */

Index	Undo handler	Redo handler	Undo style
RVEH_REPLACE (58)	log_rv_copy_char	log_rv_copy_char	physical — whole-page before-image restored on sysop abort
RVEH_INSERT (59)	ehash_rv_insert_undo	ehash_rv_insert_redo	logical — “delete this key”
RVEH_DELETE (60)	ehash_rv_delete_undo	ehash_rv_delete_redo	logical — “re-insert this key”
RVEH_INIT_BUCKET (61)	pgbuf_rv_new_page_undo	ehash_rv_init_bucket_redo	physical — page de-allocated on undo
RVEH_CONNECT_BUCKET (62)	log_rv_copy_char	ehash_rv_connect_bucket_redo	physical — undo restores before-image
RVEH_INC_COUNTER (63)	ehash_rv_increment	ehash_rv_increment	physical — symmetric +/- delta
RVEH_INIT_DIR (64)	NULL	ehash_rv_init_dir_redo	redo-only (committed create)
RVEH_INIT_NEW_DIR_PAGE (65)	pgbuf_rv_new_page_undo	ehash_rv_init_dir_new_page_redo	physical — page de-allocated on undo

Why this split. Single-key insert/delete are logical because a concurrent split may relocate the record by undo time, so a byte-level “restore slot N on page P” is wrong; the logical undo re-resolves through the directory (ehash_find_bucket_vpid_with_hash) and acts on whatever bucket now holds the key. Connect/counter and RVEH_REPLACE are physical: inside a log_sysop that either commits (no undo) or aborts (exact byte-image restore, no relocation possible). RVEH_REPLACE is the only one carrying a full DB_PAGESIZE image rather than a delta — used where the split rewrites an arbitrary fraction of a page (10.5).

ehash_rv_insert_undo is a thin adapter: it reads EHID and key (record_p += sizeof (OID) skips the assoc-value OID; the REC_BIGONE branch is compiled out, 10.6) and return ehash_rv_delete (...), bypassing merge logic. ehash_rv_delete_undo is symmetric: after reading EHID and value OID it re-inserts via ehash_insert_helper (..., S_LOCK, NULL) — which may itself split — failing under assert (er_errid () != NO_ERROR).

ehash_rv_delete is the CLR-style core shared by insert-undo: it logs only a compensating redo (RVEH_DELETE) and no undo of its own, so a second crash mid-recovery replays forward, never backward. It re-resolves via ehash_find_bucket_vpid_with_hash (... PGBUF_LATCH_READ, PGBUF_LATCH_WRITE, ...) (dir root READ, bucket WRITE) with four guards that bail before mutating — NULL dir root, NULL_PAGEID bucket VPID, NULL bucket page, or ehash_locate_slot miss — each unfixing what it holds and returning er_errid () or ER_EH_UNKNOWN_KEY. The surviving path deletes:

// ehash_rv_delete -- src/storage/extendible_hash.c
log_append_redo_data2 (thread_p, RVEH_DELETE, &ehid_p->vfid, bucket_page_p, slot_no, ...);  /* <- compensating redo */
(void) spage_delete (thread_p, bucket_page_p, slot_no); pgbuf_set_dirty (...);
/* Do NOT remove overflow pages here -- their own undo functions handle that */

If ehash_allocate_recdes for the redo image fails it sets ER_OUT_OF_VIRTUAL_MEMORY but still performs the delete: in recovery the log append is best-effort and the undo’s effect must not be abandoned.

The redo handlers are page-local replays. ehash_rv_init_bucket_redo rebuilds an empty bucket from the two-byte {alignment, local_depth} payload: set PAGE_EHASH, spage_initialize as UNANCHORED_KEEP_SEQUENCE, spage_insert the EHASH_BUCKET_HEADER into slot 0 — a non-SP_SUCCESS return is FATAL unless already SP_ERROR; either way returns er_errid (). ehash_rv_connect_bucket_redo replays idempotently: it reads EHASH_REPETITION {vpid, count} (Ch.7), loops count EHASH_DIR_RECORDs, stamps each repetition.vpid only if (!VPID_EQ (...)), dirtying only on a real change. ehash_rv_increment serves both undo and redo (signed delta; undo passes the negated one). The two directory redo handlers do not mirror the bucket initialiser: ehash_rv_init_dir_redo sets the page type then replays the logged byte image via log_rv_copy_char; ehash_rv_init_dir_new_page_redo merely stamps PAGE_EHASH and dirties. Neither runs spage_initialize. RVEH_INIT_DIR has a NULL undo because directory creation runs inside the committed xehash_create system op.

10.3 Full-scan iterators: ehash_map and ehash_apply_each

ehash_map is the only public way to visit every entry. It bypasses the directory and walks the bucket file page by page, since one bucket is reachable from many slots and a directory walk would visit duplicates.

// ehash_map -- src/storage/extendible_hash.c
if (ehid_p == NULL) { return ER_FAILED; }                         /* <- nothing fixed yet */
dir_page_p = ehash_fix_ehid_page (..., PGBUF_LATCH_READ);
if (file_get_num_user_pages (..., &num_pages) != NO_ERROR)
  { return ER_FAILED; }                                           /* <- dir_page_p NOT unfixed: a leak */
for (bucket_page_no = 0; apply_error_code == NO_ERROR && bucket_page_no < num_pages; bucket_page_no++) {
    bucket_page_p = ehash_fix_nth_page (..., PGBUF_LATCH_READ);
    if (bucket_page_p == NULL) { pgbuf_unfix_and_init (..., dir_page_p); return ER_FAILED; }
    for (slot_id = first_slot_id + 1; ...; slot_id++)             /* <- slot 0 is the header; skip */
        if (ehash_apply_each (..., &apply_error_code, ...) != NO_ERROR)
          { ...unfix bucket + dir; return ER_FAILED; }
    pgbuf_unfix_and_init (thread_p, bucket_page_p); }

The dir is held under PGBUF_LATCH_READ throughout. The exits are not uniform: (a) NULL ehid_p → ER_FAILED, nothing fixed; (b) file_get_num_user_pages failure → ER_FAILED without unfixing dir_page_p — a genuine page-leak branch worth flagging if you harden this path; (c) ehash_fix_nth_page failure and (d) ehash_apply_each error both unfix bucket + dir before ER_FAILED; (e) the soft callback stop — when the callback sets apply_error_code, the for-guard (apply_error_code == NO_ERROR) halts the scan and returns that code after the normal dir unfix. ehash_apply_each reconstructs the typed key first: DB_TYPE_STRING mallocs then frees a copy, DB_TYPE_OBJECT copies into a stack next_key, the numeric arms are compiled out, and default raises ER_EH_ROOT_CORRUPTED. ehash_dump / ehash_dump_bucket are debug-only printers.

10.4 Temporary files: logging suppressed, only a temp destructor

Every structural function threads an is_temp flag (via file_is_temp). When set it skips log_sysop_start/log_append_* entirely — temp hash tables (sort/hash-join intermediates) are never recovered. Chapter 6’s ehash_extend_bucket shows the pattern (if (!is_temp) log_sysop_start (...)), and ehash_connect_bucket guards its log_append_undoredo_data2 the same way.

xehash_destroy only handles temporary files. Two guards precede the sysop: a NULL ehid_p returns ER_FAILED, and a failed ehash_fix_ehid_page (... PGBUF_LATCH_WRITE) on the directory root returns ER_FAILED before any log_sysop_start. Past those guards, inside one log_sysop_start/log_sysop_commit pair it calls file_destroy twice — the bucket file first, then pgbuf_unfix’s the directory root, then ehid_p->vfid (each is_temp = true) — each guarded by if (... != NO_ERROR) { assert_release (false); }; temp teardown is expected infallible, so a failure is a logic bug. There is no permanent-file destructor at all: a permanent hash (only persistent user: the class-name → OID catalog) lives for the database lifetime and is reclaimed through normal file-manager teardown.

10.5 Concurrency: page latches, the split/double latch order, two-descent upgrade

There is no key- or row-level locking inside extendible hashing; the only synchronisation is the page latch (PGBUF_LATCH_READ = shared, PGBUF_LATCH_WRITE = exclusive). The design rests on one fact: the directory is one level deep — a flat array, not a tree — so there is no latch-coupling between directory levels. A reader S-latches the root, resolves a slot, latches the bucket, done.

The latch-ordering invariant. Every mutating path fixes pages in the same nesting order and unfixes inner-first, so two concurrent splits can never deadlock. Walking ehash_insert_helper → ehash_insert_bucket_after_extend_if_need → ehash_extend_bucket → ehash_split_bucket/ehash_expand_directory, the hold order is:

1. Directory root — fixed first by ehash_find_bucket_vpid_with_hash (PGBUF_LATCH_WRITE on the X pass, PGBUF_LATCH_READ on the S pass) and held to the very end of ehash_insert_helper.
2. Target bucket — ehash_insert_bucket_after_extend_if_need fixes it at PGBUF_LATCH_WRITE.
3. Sibling bucket — ehash_split_bucket allocates and fixes the new sibling at WRITE while the original bucket is still held.
4. Directory-double pages (only if new_local_depth > dir_header_p->depth) — ehash_expand_directory re-fixes the directory header at PGBUF_LATCH_WRITE, then the old and new directory data pages at WRITE, walking from the last page backward (old_dir_nth_page = old_pages, loop decrements).

// ehash_insert_bucket_after_extend_if_need -- src/storage/extendible_hash.c
bucket_page_p = ehash_fix_old_page (..., bucket_vpid_p, PGBUF_LATCH_WRITE);   /* <- step 2: bucket X */
...
sibling_page_p = ehash_extend_bucket (...);   /* <- step 3-4: sibling + dir-double, all X */

So the lock graph is a strict tree rooted at the single directory root: dir root → bucket → sibling, plus dir root → expand pages. No thread ever holds a bucket while waiting for the root, because the root is always acquired first and never re-acquired after a bucket. That total order is the deadlock-freedom argument.

Invariant — a structure-mutating insert holds the directory root in X latch before it touches any directory slot, and holds it across the bucket and sibling latches. The S pass never mutates: ehash_insert_bucket_after_extend_if_need checks if (lock_type == S_LOCK) return EHASH_BUCKET_FULL; before calling ehash_extend_bucket. The cost is the two-descent penalty — a split-causing insert reads the directory twice; the benefit is that the common case (room in the bucket) finishes under a shared root latch, so readers and non-splitting writers do not serialise on the root.

Insertion uses an optimistic S-then-X strategy. The first descent (ehash_insert_helper, lock_type == S_LOCK) S-latches the root hoping the bucket has room. Three discoveries force a restart at X:

1. The slot is NULL_VPID and a bucket must be created (10.1).
2. The bucket is full and must split — ehash_insert_bucket_after_extend_if_need returns EHASH_BUCKET_FULL under S.
3. (Compiled out) a long string would need an overflow file.

In each case the handler unfixes and tail-recurses:

// ehash_insert_helper -- src/storage/extendible_hash.c
if (VPID_ISNULL (&bucket_vpid)) {
    if (lock_type == S_LOCK) { pgbuf_unfix_and_init (...); return ehash_insert_helper (..., X_LOCK, ...); }  /* <- drop S, redescend */
    else { ...ehash_insert_to_bucket_after_create (...); } }       /* <- under X: create */
else { result = ehash_insert_bucket_after_extend_if_need (...);
       if (result == EHASH_BUCKET_FULL)
         { pgbuf_unfix_and_init (...); return ehash_insert_helper (..., X_LOCK, ...); } }   /* <- redescend to split */

This opens the concurrent-split window (companion Open Question 3): between the S-unfix and the X-fix another thread may split the same bucket. The redescent restarts at ehash_find_bucket_vpid_with_hash, which reads dir_header_p->depth fresh and re-resolves the now-different bucket; if the rival split already made room, the EHASH_BUCKET_FULL branch is not taken and the insert succeeds with no second split. It holds because every retry restarts at the root with the live depth.

stateDiagram-v2
  [*] --> S_descent: insert key
  S_descent --> Done: bucket has room
  S_descent --> Restart_X: slot NULL or BUCKET_FULL
  Restart_X --> X_descent: re-fix root at X
  X_descent --> Done: rival split made room
  X_descent --> Mutate: create or split under X
  Mutate --> Done: record inserted

Figure 10-2. Optimistic S-then-X insert latching.

flowchart TD
  R["directory root\nLATCH_WRITE, held to end"] --> B["target bucket\nLATCH_WRITE"]
  B --> S["sibling bucket\nLATCH_WRITE"]
  R --> H["dir header re-fix\nLATCH_WRITE"]
  H --> O["old/new dir pages\nLATCH_WRITE, last page backward"]

Figure 10-3. Split/double latch nesting — a tree rooted at the single directory root; unfix is inner-first, root last.

10.6 Dead code: ENABLE_UNUSED_FUNCTION paths

A large fraction of the module is fenced behind #if defined (ENABLE_UNUSED_FUNCTION) and never built — vestiges of a general extendible hash for every SQL scalar type and arbitrarily long keys. The live code supports only DB_TYPE_STRING (class names, capped at 255 bytes by assert (strlen ((char *) key_p) < 256) in ehash_insert_helper) and DB_TYPE_OBJECT (OIDs). Two dead arms matter: long-string overflow files — ehash_create_overflow_file, ehash_compose_overflow, and the REC_BIGONE branches in the two undo handlers and ehash_apply_each (sub-256-byte keys always fit one REC_HOME, so overflow_file is effectively always NULL); and numeric key types — the DB_TYPE_INTEGER … MONETARY arms of switch (key_type). The assertions plus the default ER_EH_ROOT_CORRUPTED (10.3) fence these off, so a non-string, non-OID key trips an error rather than mis-hashing silently.

10.7 Chapter summary — key takeaways

1. NULL-slot creation is one atomic structural op — ehash_insert_to_bucket_after_create picks depth via ehash_find_depth, then allocate → connect → adjust-depth under one log_sysop committed before the record write.
2. Eight RVEH_ indices, all this module’s* — including RVEH_REPLACE (58), the whole-page before-image logger the split and directory-double paths emit; recovery splits on undo style — single-key insert/delete are logical, while RVEH_REPLACE/split/connect/counter are physical inside system ops.
3. ehash_rv_delete is a CLR — it logs only a compensating RVEH_DELETE redo and no undo, so a second crash mid-recovery replays forward.
4. Redo handlers are idempotent page-local replays — and the two *_init_dir_*_redo handlers only stamp/replay the page image, unlike ehash_rv_init_bucket_redo which re-runs spage_initialize.
5. ehash_map walks the bucket file, not the directory — note its file_get_num_user_pages-failure exit leaks the dir page while the others unfix cleanly, plus the soft callback stop.
6. Temp tables suppress logging and own the only destructor — is_temp gates every log_*; xehash_destroy (after two pre-sysop guards) tears down only temp files. Permanent hashes have no destructor.
7. Concurrency is page-latch-only over a total order — the flat directory needs no latch-coupling; a split holds dir root → bucket → sibling (plus dir-double pages) as a tree rooted at the single root, and a mutating insert redescends at X re-reading the live depth.

Position hints as of this revision

The following are line numbers as observed on 2026-06-21; symbols are the canonical anchor and line numbers are hints that decay.

Symbol	File	Line
mht_1strhash	src/base/memory_hash.c	449
mht_2strhash	src/base/memory_hash.c	468
mht_3strhash	src/base/memory_hash.c	485
vpid	src/compat/dbtype_def.h	889
vfid	src/compat/dbtype_def.h	896
EHASH_OVERFLOW_RATE	src/storage/extendible_hash.c	69
EHASH_UNDERFLOW_RATE	src/storage/extendible_hash.c	81
EHASH_OVERFLOW_THRESHOLD	src/storage/extendible_hash.c	90
EHASH_UNDERFLOW_THRESHOLD	src/storage/extendible_hash.c	91
EHASH_HASH_KEY_BITS	src/storage/extendible_hash.c	94
EHASH_HASH_KEY	src/storage/extendible_hash.c	99
ehash_dir_header	src/storage/extendible_hash.c	103
EHASH_DIR_HEADER	src/storage/extendible_hash.c	103
local_depth_count	src/storage/extendible_hash.c	111
EHASH_DIR_RECORD	src/storage/extendible_hash.c	119
ehash_dir_record	src/storage/extendible_hash.c	120
EHASH_DIR_RECORD	src/storage/extendible_hash.c	120
ehash_bucket_header	src/storage/extendible_hash.c	127
EHASH_BUCKET_HEADER	src/storage/extendible_hash.c	127
EHASH_RESULT	src/storage/extendible_hash.c	132
EHASH_SUCCESSFUL_COMPLETION	src/storage/extendible_hash.c	134
EHASH_FULL_SIBLING_BUCKET	src/storage/extendible_hash.c	138
EHASH_NO_SIBLING_BUCKET	src/storage/extendible_hash.c	139
EHASH_REPETITION	src/storage/extendible_hash.c	144
ehash_repetition	src/storage/extendible_hash.c	145
EHASH_DIR_HEADER_SIZE	src/storage/extendible_hash.c	156
EHASH_MAX_STRING_SIZE	src/storage/extendible_hash.c	160
EHASH_NUM_FIRST_PAGES	src/storage/extendible_hash.c	164
EHASH_LAST_OFFSET_IN_FIRST_PAGE	src/storage/extendible_hash.c	168
EHASH_NUM_NON_FIRST_PAGES	src/storage/extendible_hash.c	172
EHASH_LAST_OFFSET_IN_NON_FIRST_PAGE	src/storage/extendible_hash.c	176
GETBITS	src/storage/extendible_hash.c	193
FIND_OFFSET	src/storage/extendible_hash.c	209
GETBIT	src/storage/extendible_hash.c	223
SETBIT	src/storage/extendible_hash.c	236
CLEARBIT	src/storage/extendible_hash.c	249
ehash_dir_locate	src/storage/extendible_hash.c	384
ehash_allocate_recdes	src/storage/extendible_hash.c	475
ehash_free_recdes	src/storage/extendible_hash.c	499
ehash_initialize_bucket_new_page	src/storage/extendible_hash.c	628
UNANCHORED_KEEP_SEQUENCE	src/storage/extendible_hash.c	661
ehash_initialize_dir_new_page	src/storage/extendible_hash.c	711
ehash_initialize_dir_new_page	src/storage/extendible_hash.c	712
ehash_rv_init_dir_new_page_redo	src/storage/extendible_hash.c	735
xehash_create	src/storage/extendible_hash.c	866
ehash_get_key_size	src/storage/extendible_hash.c	879
ehash_create_helper	src/storage/extendible_hash.c	954
ehash_fix_old_page	src/storage/extendible_hash.c	1188
ehash_fix_ehid_page	src/storage/extendible_hash.c	1218
ehash_fix_nth_page	src/storage/extendible_hash.c	1236
xehash_destroy	src/storage/extendible_hash.c	1259
ehash_find_bucket_vpid	src/storage/extendible_hash.c	1295
ehash_find_bucket_vpid_with_hash	src/storage/extendible_hash.c	1326
ehash_find_bucket_vpid_with_hash	src/storage/extendible_hash.c	1327
ehash_search	src/storage/extendible_hash.c	1379
ehash_insert	src/storage/extendible_hash.c	1461
ehash_insert_to_bucket_after_create	src/storage/extendible_hash.c	1472
ehash_extend_bucket	src/storage/extendible_hash.c	1545
ehash_extend_bucket	src/storage/extendible_hash.c	1546
ehash_insert_bucket_after_extend_if_need	src/storage/extendible_hash.c	1640
ehash_insert_bucket_after_extend_if_need	src/storage/extendible_hash.c	1641
ehash_insert_helper	src/storage/extendible_hash.c	1715
ehash_insert_to_bucket	src/storage/extendible_hash.c	1837
ehash_write_key_to_record	src/storage/extendible_hash.c	2067
ehash_compose_record	src/storage/extendible_hash.c	2172
ehash_compare_key	src/storage/extendible_hash.c	2223
ehash_binary_search_bucket	src/storage/extendible_hash.c	2401
ehash_locate_slot	src/storage/extendible_hash.c	2479
ehash_get_pseudo_key	src/storage/extendible_hash.c	2509
ehash_find_first_bit_position	src/storage/extendible_hash.c	2545
ehash_distribute_records_into_two_bucket	src/storage/extendible_hash.c	2604
ehash_split_bucket	src/storage/extendible_hash.c	2684
ehash_expand_directory	src/storage/extendible_hash.c	2792
ehash_connect_bucket	src/storage/extendible_hash.c	3067
ehash_find_depth	src/storage/extendible_hash.c	3183
ehash_check_merge_possible	src/storage/extendible_hash.c	3274
ehash_delete	src/storage/extendible_hash.c	3418
RVEH_DELETE	src/storage/extendible_hash.c	3572
ehash_shrink_directory_if_need	src/storage/extendible_hash.c	3615
ehash_adjust_local_depth	src/storage/extendible_hash.c	3633
ehash_merge_permanent	src/storage/extendible_hash.c	3655
ehash_merge	src/storage/extendible_hash.c	3771
ehash_shrink_directory	src/storage/extendible_hash.c	3982
file_numerable_truncate	src/storage/extendible_hash.c	4148
ehash_hash_string_type	src/storage/extendible_hash.c	4156
ehash_hash_eight_bytes_type	src/storage/extendible_hash.c	4244
ehash_hash	src/storage/extendible_hash.c	4347
ehash_apply_each	src/storage/extendible_hash.c	4395
ehash_map	src/storage/extendible_hash.c	4518
ehash_dump	src/storage/extendible_hash.c	4598
ehash_rv_init_bucket_redo	src/storage/extendible_hash.c	5023
ehash_rv_init_dir_redo	src/storage/extendible_hash.c	5072
ehash_rv_insert_redo	src/storage/extendible_hash.c	5089
ehash_rv_insert_undo	src/storage/extendible_hash.c	5126
ehash_rv_delete_redo	src/storage/extendible_hash.c	5181
ehash_rv_delete_undo	src/storage/extendible_hash.c	5220
ehash_rv_delete	src/storage/extendible_hash.c	5293
ehash_rv_increment	src/storage/extendible_hash.c	5405
ehash_rv_connect_bucket_redo	src/storage/extendible_hash.c	5429
ehash_read_oid_from_record	src/storage/extendible_hash.c	5456
ehash_write_oid_to_record	src/storage/extendible_hash.c	5471
ehash_write_ehid_to_record	src/storage/extendible_hash.c	5501
file_create_ehash	src/storage/file_manager.c	3261
file_create_ehash_dir	src/storage/file_manager.c	3285
file_create	src/storage/file_manager.c	3311
file_ehash_des	src/storage/file_manager.h	114
ehid	src/storage/storage_common.h	213
EH_SEARCH	src/storage/storage_common.h	386
RV_fun	src/transaction/recovery.c	407
RVEH_REPLACE	src/transaction/recovery.h	105
RVEH_INSERT	src/transaction/recovery.h	106
RVEH_DELETE	src/transaction/recovery.h	107
RVEH_INIT_BUCKET	src/transaction/recovery.h	108
RVEH_CONNECT_BUCKET	src/transaction/recovery.h	109
RVEH_INC_COUNTER	src/transaction/recovery.h	110
RVEH_INIT_DIR	src/transaction/recovery.h	111
RVEH_INIT_NEW_DIR_PAGE	src/transaction/recovery.h	112

Sources

• cubrid-extendible-hash.md — the high-level companion. See also cubrid-disk-manager-detail.md (the numerable file type ehash files use).
• Code: src/storage/extendible_hash.{c,h}.
• Methodology: knowledge/methodology/code-analysis-detail-doc.md.