Resource Allocation

12.1 built a manager that can answer whether a request can be served. It never answers where.

This chapter is about that word, and about how much has to happen between deciding and the host being able to use the memory.

1. The Engineering Problem — The Word "Where"

The admission gate in 12.1 compares a request against free capacity and against the largest free extent. If both tests pass, some extent can hold the request. Usually more than one can, and picking among them is a decision with consequences that arrive later.

The choice changes the shape of what remains. Taking a four-unit run to satisfy a two-unit request leaves two units that may never be big enough for anything. Taking an exact two-unit hole leaves the four-unit run intact. Both grants succeed. Only one of them keeps the next request serviceable, and nothing in the grant itself reveals which.

And the grant is not the end. A bit set in a bitmap says nothing about whether the ownership record exists, whether the addressing has been enabled, or whether a second requester might be handed the same units while the first is still arriving. Between this capacity is yours and you can use it there is a sequence of states, and every one of them is a window where something can go wrong.

Returns are worse. Handing capacity back is not the reverse of taking it. The old owner's accesses have to be gone — demonstrably, not presumably — before anyone else can be given the same units. Skipping that is not a performance optimisation; it is a data-disclosure bug.

This chapter builds the allocator that makes the placement decision, the split and merge that maintain the free extents, and the two lifecycles that turn a decision into a usable allocation and back again.

2. The One-Sentence Model

Allocation is a lifecycle, not a bitmap write. The search picks a place, the split makes it fit, the reserve takes it off the market, the record makes it owned, the activation makes it reachable — and the return runs the whole thing backwards with evidence at each step.

Call it choose, reserve, own, activate. Anything that skips a step hands out capacity that somebody else can still be given, or that the host cannot yet reach, or that the previous owner can still see.

3. What This Chapter Owns

Deferred:

The border with 15.4 is worth stating plainly, because both chapters contain the words dynamic and allocation. 15.4 is about a fabric manager binding resources to hosts across a discovered topology — who is allowed to talk to what, and how that is arranged and rearranged. This chapter is about the allocator itself: which extent, split how, and through what sequence of states. There is no fabric here, no manager redundancy, no discovery and no topology.

4. Teaching-model boundary

The freely available public material describes what pooling makes possible, not how a pool manager chooses extents. So this chapter invents an allocator and says so.

The two policies below are the classic textbook pair. They are used here because their difference is easy to measure and impossible to argue away, not because either is mandated. A real implementation might use neither. What transfers is the finding: the placement decision, not the capacity, decides whether the next request succeeds — and that is a property of allocators, not of any interconnect.

5. RTL 1 and 2 — Two Policies, One Bitmap

Both policies answer the same question — which extent — and disagree about the answer.

// FIRST FIT: the lowest base that can hold the request.
module first_fit #(parameter int UNITS = 16) (
  input  logic [UNITS-1:0] map_in,        // 1 = allocated
  input  logic [4:0]       size,
  output logic             found,
  output logic [3:0]       base
);
  // Two rules the loops must obey to be both terminating and synthesizable:
  // the counters are one bit wider than the map index, because a counter
  // exactly as wide as the bound wraps to zero when an oversized request makes
  // the bound underflow; and both bounds are CONSTANT, with the variable part
  // of the condition moved inside as a guard.
  logic [5:0] s, k, base6;
  logic       ok;
  always_comb begin
    found = 1'b0; base6 = 6'd0;
    for (s = 6'd0; s < UNITS[5:0]; s = s + 6'd1) begin
      if ((size != 5'd0) && ((s + {1'b0, size}) <= UNITS[5:0])) begin
        ok = 1'b1;
        for (k = 6'd0; k < UNITS[5:0]; k = k + 6'd1)
          if ((k < {1'b0, size}) && map_in[s + k]) ok = 1'b0;
        if (ok && !found) begin found = 1'b1; base6 = s; end
      end
    end
  end
  assign base = base6[3:0];
endmodule

Best fit scans the map for maximal free runs and keeps the smallest one that is still big enough.

module best_fit #(parameter int UNITS = 16) (
  input  logic [UNITS-1:0] map_in,
  input  logic [4:0]       size,
  output logic             found,
  output logic [3:0]       base,
  output logic [4:0]       chosen_len
);
  logic [5:0] i, base6;
  logic [4:0] run, best_len;
  logic       cur_free;
  always_comb begin
    found = 1'b0; base6 = 6'd0; best_len = 5'd31; chosen_len = 5'd0;
    run = 5'd0;
    // The i == UNITS pass flushes a run that reaches the top of the map, so
    // an extent ending at the top edge is evaluated like any other.
    for (i = 6'd0; i <= UNITS[5:0]; i = i + 6'd1) begin
      cur_free = (i < UNITS[5:0]) ? ~map_in[i] : 1'b0;
      if (cur_free) begin
        run = run + 5'd1;
      end else begin
        if ((size != 5'd0) && (run >= size) && (run < best_len)) begin
          best_len   = run;
          chosen_len = run;
          base6      = i - {1'b0, run};
          found      = 1'b1;
        end
        run = 5'd0;
      end
    end
  end
  assign base = base6[3:0];
endmodule

On bitmap 0x0F30 — free extents of 4, 2 and 4 units — a two-unit request measures:

Both grants succeed. Section 14 measures what that difference costs eight operations later.

Neither policy invents capacity. Asking 0x0F30 for five contiguous units is refused by both, with 10 units free — the 12.1 lesson holding under a real allocator.

6. RTL 3 — Ranges, Applied Whole Or Not At All

An allocator writes ranges, and a range operation that half-succeeds is worse than one that fails.

module range_map #(parameter int UNITS = 16) (
  input  logic clk, rst_n,
  input  logic set_en, input logic [3:0] set_base, input logic [4:0] set_len,
  input  logic clr_en, input logic [3:0] clr_base, input logic [4:0] clr_len,
  output logic [UNITS-1:0] map_q,
  output logic [4:0] used_cnt,
  output logic overlap_err, clr_unowned_err, set_ok, clr_ok
);
  logic [5:0] j;
  logic set_clean, clr_clean;
 
  // Both range checks run over the whole map with a constant bound and an
  // in-range guard, so the loops synthesise and cannot run away.
  always_comb begin
    set_clean = 1'b1; clr_clean = 1'b1;
    for (j = 6'd0; j < UNITS[5:0]; j = j + 6'd1) begin
      if (set_en && (j >= {2'b0, set_base}) && (j < {2'b0, set_base} + {1'b0, set_len})
          && map_q[j]) set_clean = 1'b0;
      if (clr_en && (j >= {2'b0, clr_base}) && (j < {2'b0, clr_base} + {1'b0, clr_len})
          && !map_q[j]) clr_clean = 1'b0;
    end
  end
 
  assign set_ok = set_en && set_clean && (set_len != 5'd0)
                  && (({2'b0, set_base} + {1'b0, set_len}) <= UNITS[6:0]);
  assign clr_ok = clr_en && clr_clean && (clr_len != 5'd0)
                  && (({2'b0, clr_base} + {1'b0, clr_len}) <= UNITS[6:0]);
endmodule

Three behaviours, all measured:

Partial application is the failure mode this prevents. If a four-unit allocation lands on two units because the other two were taken, the requester believes it holds four, addresses four, and reads somebody else's memory in two of them. Refusing the whole operation leaves the pool in a state everyone still agrees about.

Set and clear on disjoint ranges in the same cycle both apply — measured at 6 units used after allocating 2 while returning 4. Concurrency is normal; overlap is not.

7. Waveform — A Grant Is Six Cycles, Not One

Transcribed from the printed trace of the lifecycle model in section 10.

Read the two output rows against each other.

grantable falls at cycle 1 and visible does not rise until cycle 6. For five cycles the capacity belongs to a request that cannot yet use it, and to nobody else at all. A design that keeps it grantable during that window can hand the same units to a second requester; a design that makes it visible early lets a host address memory whose ownership record does not exist yet.

owned rises one cycle after reserved. Reserving is taking it off the market; owning is writing down who has it. They are separate because the first must happen before the search can be repeated for anyone else, and the second must happen before anything is allowed to reach it.

The trace also holds cycle 4 and 5 in ACTIVATE with act_ack low. The run extends this to four cycles and confirms visible stays low throughout: activation is a wait on external evidence, not a fixed delay.

8. RTL 4 — Splitting The Extent You Chose

The chosen extent is almost always bigger than the request, and the remainder has to return to free capacity correctly described.

module extent_split (
  input  logic clk, rst_n,
  input  logic       split_en,
  input  logic [3:0] ext_base,
  input  logic [4:0] ext_len, req_len,
  output logic [3:0] alloc_base, output logic [4:0] alloc_len,
  output logic [3:0] rem_base,   output logic [4:0] rem_len,
  output logic       rem_valid, split_ok, split_err,
  output logic [7:0] n_split, n_exact, n_err
);
  logic too_big, exact;
  assign too_big   = split_en && (req_len > ext_len);
  assign exact     = split_en && (req_len == ext_len) && (req_len != 5'd0);
  assign split_ok  = split_en && !too_big && (req_len != 5'd0);
  assign split_err = too_big;
 
  assign alloc_base = ext_base;
  assign alloc_len  = split_ok ? req_len : 5'd0;
  // The remainder begins exactly where the allocation ends. An off-by-one here
  // either leaks a unit or hands the same unit out twice.
  assign rem_base   = ext_base + req_len[3:0];
  assign rem_len    = split_ok ? (ext_len - req_len) : 5'd0;
  assign rem_valid  = split_ok && (ext_len != req_len);
endmodule

Measured: an eight-unit extent at base 4, asked for three units, yields an allocation of 3 at base 4 and a remainder of 5 units at base 7.

That arithmetic carries the whole model, and the testbench asserts a conservation law on every split — allocated plus remainder equals the original extent. The two ways to get it wrong are exactly one unit apart and have opposite consequences:

The second is a double allocation that no ownership check catches, because both records are internally consistent.

An exact fit is a different case, not a split: rem_valid stays low and the exact-fit counter moves instead. Over the run, 3 genuine splits, 2 exact fits, 1 oversized request refused. Keeping them apart matters operationally — a pool serving mostly exact fits is well matched to its workload, and one serving mostly splits is grinding its extents smaller with every grant.

9. RTL 5 — Coalescing On Return

Without a merge on return, every allocation leaves a hole exactly its own size and the pool fragments monotonically. It never recovers, because nothing ever makes two small extents into one big one.

module extent_merge #(parameter int UNITS = 16) (
  input  logic [UNITS-1:0] map_in,       // the map AFTER the range is cleared
  input  logic [3:0]       base,
  input  logic [4:0]       len,
  output logic [3:0]       merged_base,
  output logic [4:0]       merged_len,
  output logic             merge_left, merge_right
);
  logic [6:0] lb, re, j, span;
  always_comb begin
    lb = {3'b0, base};
    re = {3'b0, base} + {2'b0, len};       // one past the end of the returned range
    // Extend only across units that are ACTUALLY free and ACTUALLY adjacent.
    // Skipping an allocated unit here merges two extents that are not
    // neighbours and hands a live allocation to the next requester.
    for (j = 7'd0; j < UNITS[6:0]; j = j + 7'd1) begin
      if ((lb > 7'd0) && !map_in[lb - 7'd1]) lb = lb - 7'd1;
      if ((re < UNITS[6:0]) && !map_in[re])  re = re + 7'd1;
    end
    merge_left  = (lb != {3'b0, base});
    merge_right = (re != ({3'b0, base} + {2'b0, len}));
    span        = re - lb;
  end
  assign merged_base = lb[3:0];
  assign merged_len  = span[4:0];
endmodule

Returning units 4 through 7 measures three different results depending on the neighbours:

The adjacency test is the safety property. Extending across an allocated unit would merge two extents that are not neighbours, and the merged extent would contain a live allocation — which the next requester would be handed. The !map_in[...] term is the only thing preventing that, and the mutation that removes it is killed by the isolated-return case.

10. RTL 6 — The Allocation Lifecycle

  // Capacity is off the market from RESERVE onward, not from LIVE. Anything
  // that becomes grantable again between reserving and going live can be
  // handed to a second requester while the first is still arriving.
  assign reserved  = (st_q == L_RESERVE) || (st_q == L_OWN)
                  || (st_q == L_ACTIVATE) || (st_q == L_LIVE);
  assign owned     = (st_q == L_OWN) || (st_q == L_ACTIVATE) || (st_q == L_LIVE);
  assign visible   = (st_q == L_LIVE);
  assign grantable = (st_q == L_IDLE);

The testbench walks the machine and asserts the exact output vector in every state, which is what makes ordering mutations die:

Two invariants are checked on every cycle of the trace rather than at the end: visible implies owned, and reserved implies not grantable. Either one failing on any cycle is a double-allocation hazard.

A failed search returns to IDLE immediately and the capacity becomes grantable again — measured, with the failure counted. Holding a reservation for a search that found nothing is a leak with no owner to blame.

A request arriving mid-lifecycle raises req_while_busy_err and leaves the live allocation untouched.

11. RTL 7 — The Reclaim Lifecycle

Returning capacity is the harder direction, because the thing that must be true — the old owner cannot still reach this — is a statement about the past.

      R_IDLE:    if (release_req) st_n = R_QUIESCE;
      // Quiesce is a WAIT, not a delay. It ends when the evidence arrives.
      R_QUIESCE: if (outstanding == 4'd0) st_n = R_RETIRE;
      R_RETIRE:  st_n = R_SCRUB;
      R_SCRUB:   if (cnt_q >= SCRUB_CYCLES[3:0] - 4'd1) st_n = R_RELEASE;
      R_RELEASE: st_n = R_IDLE;

Measured: with three accesses in flight, quiesce held for all six cycles they remained outstanding, and reusable was asserted low on every one of them. The scrub then occupies exactly its full four cycles, with reusable low throughout, and rises only in RELEASE.

Quiesce being a wait rather than a delay is the whole point. A fixed delay is a guess about how long accesses take, and a guess that is wrong once is a data-disclosure bug. The FSM waits for the count to reach zero, however long that is.

12. RTL 8 — Requests That Wait, And Requests That Give Up

Allocation is not instantaneous, so requests queue. A request that waits forever is worse than a refused one: the requester is blocked and no counter explains why.

  // A timed-out head is dropped and NOT granted, so the pop is not serviced in
  // the same cycle -- granting a request that has already been abandoned is
  // how a requester ends up owning capacity it stopped waiting for.
  logic do_drop, do_pop, do_push, removes;
  always_comb begin
    do_drop = (cnt_q != 3'd0) && (q_age[0] >= TIMEOUT[4:0]);
    do_pop  = pop && !do_drop && (cnt_q != 3'd0);
    removes = do_drop || do_pop;
    do_push = push && ((cnt_q - {2'b0, removes}) < DEPTH[2:0]);
  end
  // ONE combined next-state for the occupancy count.
  cnt_q <= cnt_q - {2'b0, removes} + {2'b0, do_push};

Measured behaviours:

The last row is the one that needed a deliberate test. Servicing a pop on the exact cycle the head times out grants capacity to a requester that has already given up — it now owns memory it will never use and may never return. The !do_drop term prevents it, and nothing in an ordinary test sequence ever reaches that cycle.

The occupancy count is a single combined next-state expression, for the reason established repeatedly in this curriculum: a push and a removal in the same cycle must both be accounted for.

13. RTL 9 — Reserved Is Not Free And Not Owned

The lifecycle in section 10 has a state where capacity belongs to nobody and must belong to nobody else. Accounting has to represent it.

module alloc_accounting #(parameter int TOTAL = 32) (
  input  logic clk, rst_n,
  input  logic rsv_en, input logic [5:0] rsv_n,   // free -> reserved
  input  logic cmt_en, input logic [5:0] cmt_n,   // reserved -> owned
  input  logic rel_en, input logic [5:0] rel_n,   // owned -> free
  input  logic abt_en, input logic [5:0] abt_n,   // reserved -> free
  output logic [5:0] free_q, rsv_q, own_q, grantable,
  output logic accept, underflow_err
);
  // ... one combined delta across all four events, then:
  assign accept = any_ev & feasible;
  // Reserved capacity is deliberately absent from this sum.
  assign grantable = free_q;

Measured: reserving 8 units of 32 leaves free=24, reserved=8, and grantable=24. The reserved units are counted, owned by nobody, and offered to nobody.

Four transitions, and the fourth is the one people forget:

Without the abort path, every activation that fails to complete strands its reservation permanently — capacity that is not free, not owned, and invisible to any leak check that only compares free against owned. Measured: a 6-unit reservation aborted returns cleanly to 32 free.

Committing more than was reserved is refused with underflow_err and leaves the reservation intact.

14. Quantitative Reasoning

The policy argument is usually conducted with adjectives. It does not have to be.

The experiment runs one workload against two independent maps, one allocated by first fit and one by best fit, and measures what is left. Seven allocations and two returns, identical on both sides:

  A=4  B=4  C=2  D=2        both maps identical: 0x0FFF
  return A (0-3)            free: 0-3, 8-9, 12-15
  return C (8-9)            10 units free in 3 extents, largest 4
  E=2   <- the policies diverge here
  F=4
  G=4   <- and here is the consequence

At E, first fit takes base 0 and breaks the four-unit run; best fit takes base 8, the exact two-unit hole. Both grants succeed and nothing looks wrong.

At G, both maps hold exactly four free units:

Identical capacity. Identical workload. One pool can serve the request and the other cannot. Over the sequence, first fit granted 6 and refused 1; best fit granted 7 and refused 0.

This is the number to take from the chapter. Placement is not a tuning parameter — it changes what the pool can do next, and the effect is invisible at the moment the decision is made.

Four metrics, and what each is for:

Utilisation answers whether to buy capacity. It is identical for both policies here, which is exactly why it cannot settle the argument.

Largest free extent answers whether the next request can be served. It differs by a factor of two on identical capacity.

Fragment count answers whether the policy is degrading. Rising fragments at flat free capacity is a policy signature, and the first-fit map ends with twice as many fragments in half the extent size.

Allocation efficiency — requested over reserved — is unchanged by placement policy, because it comes from granularity rather than from choice. It belongs to 12.1 and is included here only to keep it out of this argument.

Neither policy wins in general. Best fit produced the better outcome on this workload and it does not always: it leaves behind the smallest possible remainders, which on a different request mix produces a pool full of one-unit holes faster than first fit would. First fit is also cheaper — it stops at the first match, where best fit must scan the entire map every time. The honest statement is that the policy must be chosen against a measured request-size distribution, and the pool must publish the counters that reveal when the choice was wrong.

15. Assertions

Written as SystemVerilog for the reader, executed as procedural checker logic — the available simulator does not run concurrent assertions, as section 17 records.

A grant is inside the map and inside a free extent.

property p_grant_in_bounds;
  @(posedge clk) disable iff (!rst_n)
    found |-> (({2'b0, base} + {1'b0, size}) <= UNITS);
endproperty

Best fit never chooses an extent smaller than the request.

property p_best_fit_sufficient;
  @(posedge clk) disable iff (!rst_n)
    bf_found |-> (chosen_len >= size);
endproperty

A range operation is all or nothing.

property p_range_atomic;
  @(posedge clk) disable iff (!rst_n)
    (set_en && !set_clean) |-> !set_ok && $stable(map_q);
endproperty

Split conserves the extent.

property p_split_conserves;
  @(posedge clk) disable iff (!rst_n)
    split_ok |-> ((alloc_len + rem_len) == ext_len);
endproperty

A merge never crosses an allocated unit.

property p_merge_adjacent;
  @(posedge clk) disable iff (!rst_n)
    merge_left |-> !map_in[merged_base];
endproperty

Visibility implies ownership — checked on every cycle, not at the end.

property p_visible_owned;
  @(posedge clk) disable iff (!rst_n)
    visible |-> owned;
endproperty

Reserved capacity is never grantable.

property p_reserved_not_grantable;
  @(posedge clk) disable iff (!rst_n)
    reserved |-> !grantable;
endproperty

Capacity is not reusable until the old owner is retired and the scrub is done.

property p_reuse_after_scrub;
  @(posedge clk) disable iff (!rst_n)
    reusable |-> (scrub_cnt >= SCRUB_CYCLES - 1) && (outstanding == 0);
endproperty

A timed-out request is dropped, never granted.

property p_timeout_not_granted;
  @(posedge clk) disable iff (!rst_n)
    timeout_drop |-> !do_pop;
endproperty

Three-phase accounting is conserved.

property p_three_phase;
  @(posedge clk) disable iff (!rst_n)
    (free_q + rsv_q + own_q) == TOTAL;
endproperty

113 assertion sites — 92 across the nine models, 18 in the policy experiment, 3 in the waveform trace. All pass.

16. Mutation Testing

59 mutations injected, 59 killed, 0 surviving.

Representative kills:

Three mutations did not die on the first run. All three were stimulus, not checkers.

The third is worth its own note. The obvious abuse request — re-allocate a range that is already allocated — proves nothing, because setting a set bit changes no state. The range has to straddle the boundary between allocated and free units so that a wrongly-applied operation is visible in the occupancy count. An abuse case that cannot change the outcome is not an abuse case.

The taxonomy has now held for six consecutive batches: escapes are stimulus gaps, unreachable checkers, or late sampling. Never a missing checker.

17. Verification Strategy

Tool reality. Icarus Verilog 13.0, which does not execute concurrent SVA. Every property in section 15 has an executable procedural counterpart and the reported numbers come from those.

Icarus also does not enforce unique/priority, and it rejects an enum-valued ternary without an explicit cast — the state machines here use if/else rather than ? : for that reason.

Every run is bounded by a hard timeout. This is not caution; a wrapping loop counter in the first version of first_fit produced a hang rather than a failure, and a testbench that reports PASS or FAIL cannot classify a simulation that never returns.

Independent oracles.

The search models matter most here. A testbench that recomputes first fit to check first fit proves only that the design agrees with itself, so every expected base and length in tb_fit_search is a literal written by hand from the bitmap. It is more tedious and it is the only version that can find a wrong answer.

Coverage. The points that matter are request size class, extent size class, outcome, lifecycle state, and queue occupancy. The two crosses worth driving are request size against extent size — which is where first fit and best fit diverge, and a single-size workload cannot distinguish them at all — and lifecycle state against a second incoming request, which is where reservation leaks and double allocation live. A cross of every base against every size is noise: the design treats units symmetrically.

18. Synthesis and Implementation Reality

The search is the expensive part, and best fit is the expensive search. First fit can stop at the first match; best fit must examine every extent before it knows which is smallest. As combinational logic neither stops early — both unroll into the full comparison structure — so the difference shows up as area rather than time, and both are deep.

The depths differ in kind. First fit is a wide OR-reduction over candidate positions, each an AND over the request width. Best fit is a sequential scan with a carried run length, so its critical path grows with the number of units, not with the request size.

Neither is acceptable flat at realistic scale. The practical structures are the same ones section 18 of 12.1 reaches for:

The last one is what most real allocators become: extents are binned by size class and the search becomes a lookup, which trades placement precision for a bounded, shallow decision. That is a policy compromise made for timing reasons, and it should be recognised as such rather than described as an optimisation.

The pipelined case has a hazard worth naming. If the search takes several cycles and the map changes underneath it, the extent it returns may no longer be free. The reservation in section 10 is what closes this: the decision is re-validated at RESERVE, and a stale result is discarded rather than granted. A pipelined allocator without a revalidation step is a double allocation waiting for a concurrent return.

The queue and the accounting are cheap — a handful of entries and three counters — and the lifecycles are five and six states. The whole cost of this chapter is in the search.

19. Silicon Observability

The two most valuable are the least obvious. A stuck rsv_q is the signature of the abort path being missing or broken, and it is invisible to any leak check that compares only free against owned — the capacity is in neither. And late_access_err versus a silent scrub failure are the same symptom with different causes, so without it the investigation begins by suspecting the wrong subsystem.

20. Debug Lab

    first fit : free=4 largest=2 frags=2  granted=6 refused=1
    best fit  : free=4 largest=4 frags=1  granted=7 refused=0

if ((size != 5'd0) && (run >= size) && (run < best_len)) begin
  best_len = run; base6 = i - {1'b0, run}; found = 1'b1;
end

logic [5:0] s, k;                              // one bit wider than the index
for (s = 6'd0; s < UNITS[5:0]; s = s + 6'd1)   // CONSTANT bound
  if ((size != 5'd0) && ((s + {1'b0, size}) <= UNITS[5:0])) begin

  overlapping allocation  : overlap_err=1, map unchanged

assign set_ok = set_en && set_clean && (set_len != 5'd0)
                && (({2'b0, set_base} + {1'b0, set_len}) <= UNITS[6:0]);

  extent 8 at base 4, request 3 : remainder 5 units at base 7

assign rem_base  = ext_base + req_len[3:0];
assign rem_len   = split_ok ? (ext_len - req_len) : 5'd0;
assign rem_valid = split_ok && (ext_len != req_len);

  return 4-7 with both sides free : merged base=0 len=12

if ((lb > 7'd0) && !map_in[lb - 7'd1]) lb = lb - 7'd1;
if ((re < UNITS[6:0]) && !map_in[re])  re = re + 7'd1;

assign visible = (st_q == L_LIVE);
// and the property, checked every cycle:  visible |-> owned

  reclaims completed=1  late access after quiesce: err=1

R_QUIESCE: if (outstanding == 4'd0) st_n = R_RETIRE;   // a wait, not a delay

  reserve 8 of 32 : free=24 reserved=8 grantable=24

if (abt_en) begin dR = dR - $signed({3'b0, abt_n}); dF = dF + $signed({3'b0, abt_n}); end

21. Design Review

What a reviewer should attack first.

The revalidation step. If the search is pipelined, ask what happens when the map changes between the search and the write. The answer must be that the reservation revalidates and discards a stale result. Without it, a concurrent return produces a double allocation, and it will only reproduce under load.

The abort path. Every reservation must be able to end in failure. Ask specifically what happens when an activation never acknowledges — if the answer is "it retries", ask what releases the reservation while it retries.

The timeout and the pop. Ask what happens when a request times out on the same cycle it would have been granted. If the design cannot say, it grants capacity to requesters that have stopped waiting.

Quiesce. If it is a counter rather than a wait, reject it. A fixed delay is a guess about access latency and the failure mode is data disclosure.

The policy, explicitly. First fit and best fit are both defensible. What is not defensible is not knowing which one is implemented, or choosing it without a request-size distribution.

What is deliberately not here. No host identity — every allocation in this chapter is anonymous, and 12.3 adds the owner, the generation and the reassignment rules. No physical placement across devices or enclosures — 12.4. No fabric manager, no discovery, no topology — Module 15. No switch — Module 16.

22. How This Appears in Real Engineering

In architecture review, the allocator is usually the last thing specified and the first thing that causes production incidents. The reason is that its failures are delayed: a placement decision made now produces a refused allocation an hour later, and nothing connects them without the fragment counter.

In RTL design, the search is the part that will not close timing, and the reflex is to pipeline it. That is correct and it introduces the stale-map hazard, which is why the reservation exists. Teams that pipeline the search without adding revalidation ship a double allocation that only appears under concurrent load.

In verification, the hard cases are the same three every time: a return landing in the same cycle as a grant, a timeout coinciding with a service, and a search whose result goes stale. All three are single-cycle coincidences, and none appears in a test written from a specification.

In bring-up, the reservation leak is the one that wastes the most time, because it is invisible to the obvious check. Free plus owned does not equal the total, and everyone stares at the returns.

In operations, the request that matters is the one this chapter's counters answer: is the pool full, or is it fragmented, or is the allocator just slow? Those are n_reject, frags, and n_timeout, and a pool that publishes only utilisation cannot distinguish them.

23. Common Misconceptions

"The allocator just finds a free extent." Finding it is the cheap part. Reserving it, recording it, activating it, and being able to abandon it are the parts that make it safe.

"Best fit is better." Measured better on the workload in section 14, and not in general: it leaves the smallest possible remainders, which on a different request mix fragments faster. It is also the more expensive search.

"Placement is a performance question." It is an availability question. Both policies granted every request that was servable; the first-fit pool then could not serve a request the best-fit pool could, from identical free capacity.

"A grant is a bitmap write." The measured lifecycle spends five cycles between the capacity leaving the grantable pool and the host being able to reach it. Every one of those cycles is a state something can go wrong in.

"Reserved capacity is basically allocated." It is neither free nor owned, and if the abort path is missing it is stuck there permanently — invisible to any leak check comparing free against owned.

"Quiesce is a delay." It is a wait on evidence. A delay is a guess about access latency, and being wrong once discloses one host's data to another.

"An exact fit is a split with a zero remainder." Treating it that way marks a zero-length remainder valid and puts a phantom extent in the free list. The counters are separate for a reason.

"Coalescing is an optimisation." Without it the pool fragments monotonically and never recovers, because nothing ever joins two holes.

24. Interview Reasoning

25. Exercises

1. Calculation. A 16-unit pool holds free extents of 6, 3 and 3 units. A stream of requests arrives sized 3, 3, 2, 4. Work through both first fit and best fit, and state after each grant the largest free extent and the fragment count. Identify the first request where the two policies produce different outcomes.

2. Analysis. A pool refuses a request while reporting 30% utilisation. Give the three measurements that distinguish exhaustion, fragmentation, and an allocator that is simply slow, and state what each would read in the three cases.

3. RTL task. Extend best_fit to break ties by preferring the lowest base. State what the current design does on a tie, why the tie-break matters for reproducibility, and design the stimulus that proves the tie-break is being exercised rather than accidentally satisfied.

4. Assertion task. Write the property proving that a merged extent never contains an allocated unit. Then explain why checking only the merged length is insufficient, and construct the bitmap on which a length-only check passes while the merge is wrong.

5. Design task. Redesign the search as a two-stage pipeline. Specify exactly what must be revalidated in the second stage, what the design does when revalidation fails, and prove that a concurrent return between the stages cannot produce a double allocation.

6. Testbench design. Design the stimulus that distinguishes a quiesce implemented as a wait from one implemented as a fixed delay. Explain why a test in which accesses always drain quickly cannot distinguish them, and state the minimum number of outstanding accesses required.

7. Debug task. Free capacity declines by a few units per day. The sum of all host allocations does not account for it and no return has failed. Give your investigation order, name the counter that identifies the cause, and explain why the obvious leak check cannot see this class of leak.

8. Design review. A colleague proposes replacing best fit with a size-class lookup for timing reasons, arguing that placement precision is a second-order concern. Give the strongest version of that argument, name the workload shape that makes it fail, and state which counter would show the failure in production before any host noticed.

26. Summary

Allocation is a lifecycle, not a bitmap write.

• Placement decides what the pool can do next. After an identical workload, both maps held 4 free units; first fit held them as 2 fragments with a largest extent of 2 and best fit as 1 extent of 4. First fit granted 6 and refused 1; best fit granted 7 and refused 0.
• Neither policy is correct in general. Best fit won this workload, costs a full scan every time, and leaves the smallest possible remainders — which on a different request mix fragments faster.
• A range is applied whole or not at all. A partially-allocated range is refused entirely with overlap_err, and the map is unchanged — because a requester that believes it holds four units and was given two will address all four.
• A split must conserve its extent. An 8-unit extent at base 4 asked for 3 yields a remainder of 5 units at base 7, and one unit either way is a permanent leak or a double allocation that no ownership check catches.
• Coalescing is not an optimisation. Returning 4 units with free neighbours on both sides produces a 12-unit extent; without the merge the pool fragments monotonically and never recovers.
• A grant takes six cycles. Capacity stops being grantable at cycle 1 and becomes visible at cycle 6, and activation is a wait — held for four cycles with the acknowledgement low, visible never rose.
• Quiesce is evidence, not a delay. It held for all 6 cycles three accesses remained in flight, the scrub then took its full 4 cycles, and an access injected afterwards raised late_access_err.
• A timed-out request is dropped, never granted — measured by popping on the exact timeout cycle and confirming nothing was granted.
• Reserved capacity is neither free nor owned, so a missing abort path leaks capacity that a free-versus-owned check cannot see. Reserving 8 of 32 leaves free=24, reserved=8, grantable=24.
• Verification: 113 assertion sites, 59 of 59 mutations killed, zero surviving. Three first-run escapes were two stimulus gaps and one case unreachable in the integration harness. The baseline found a non-terminating search loop — a hang, not a wrong answer — and a silently vacuous assertion on an uninitialised value, which hardened every checker in the batch.

Next: 12.3 Multi-Host Systems, which gives every allocation in this chapter something it currently lacks — an owner with an identity. Hosts that join, leave, reset and fail; generations that stop a late event from corrupting a reused entry; and the reassignment rules that this chapter's lifecycle was built to make possible.