TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Circular FIFO Design: Wraparound, Overwrite-Oldest Mode and Peek (FIFO Series, Part 9)

The Semiconductor Hub
by
0
Share Facebook X LinkedIn WhatsApp Email
Hand-drawn cover card for FIFO Series Part 9, Circular FIFO, with a sketch of entries moving from push to pop.

Every FIFO in this series is circular underneath: the storage is used as a ring and the pointers wrap. Part 1 treated that ring as plumbing. This part looks at it directly, because two things happen at the wrap that are easy to get wrong. One is the set of simultaneous operations at the boundary, where the next write slot and the oldest entry are the same slot. The other is a behavior many designs actually want at that boundary: when the ring is full, keep the newest data and quietly drop the oldest.

This is Part 9 of the FIFO Series: the circular FIFO. We go through the four cases at the full boundary, add an overwrite-oldest mode with a sticky "data was lost" flag, and add a peek port that reads any stored entry by its age, which is what trace and debug buffers need.

Key takeaways

  • At the full boundary the write slot and the oldest entry are the same slot. Every combination of push and pop there needs a defined result.
  • A normal FIFO refuses a push when full unless a pop happens in the same cycle. A circular buffer in overwrite mode accepts it, drops the oldest entry, and moves both pointers together.
  • Overwrite mode must leave a trace: a sticky lost flag, or a drop counter, so software knows the history is incomplete.
  • A peek port at rptr + offset reads any stored entry by age without popping it, which suits trace buffers and debug readout.
  • Test both modes, with the pointers wrapping many times and every case at the full boundary hit at every slot.

In this part

What problem it solves

A normal FIFO is lossless: when it is full, the producer waits. That is right for data that must arrive, such as bus transactions or packets. It is wrong for a different class of data, where the producer cannot or must not wait and only the most recent history matters. A trace buffer recording the last few hundred bus transactions before a hang, an event log inside a power controller, a buffer of recent sensor samples, or a history of branch outcomes all want the same thing: never stall the source, and keep the newest DEPTH entries.

A circular buffer with an overwrite mode serves both classes with one block. In normal mode it is the FIFO of Part 1. In overwrite mode it is a ring of the most recent entries.

The interface

The base interface is Part 1's: push, wdata, full, pop, rdata and empty. Three additions make it a circular buffer:

  • overwrite: a mode input, usually static or set by software. When high, a push into a full ring drops the oldest entry instead of being refused.
  • lost and clr_lost: a sticky flag set whenever an entry is dropped, cleared by software after it has read the buffer.
  • peek_off and peek_data: a read of the entry peek_off places behind the oldest, without moving any pointer.

The four cases at the full boundary

Hand-drawn table of the four cases at the full boundary: push only is refused in normal mode and evicts the oldest in overwrite mode, pop only pops in both, push and pop together use the same slot in both, and neither holds.

When the ring is full, the write pointer has come all the way around to the oldest entry. The four input combinations then behave as follows.

  • Push only. In normal mode it is refused, and an assertion should flag it if the producer was not supposed to try. In overwrite mode the push is accepted, the new entry is written into the oldest entry's slot, and the read pointer moves forward with the write pointer.
  • Pop only. The same in both modes: the oldest entry leaves and the ring is no longer full.
  • Push and pop. The same in both modes and the case that most often hides a bug. The pop reads the slot and the push writes the same slot. With a registered read from flops, the read gets the old value and the write lands at the clock edge, which is exactly right. With memory, check the read-during-write behavior, as Part 1 warned.
  • Neither. Nothing changes.

The middle two rows are identical in both modes. Overwrite mode only changes the first row, which makes it a cheap addition to an ordinary FIFO.

Overwrite mode

Hand-drawn ring of eight slots holding A to H, full with the read and write pointers on A's slot; after a push of I in overwrite mode, I replaces A and both pointers move to B's slot.

The ring diagram shows the eviction. The ring holds A to H with both pointers at A's slot. A push of I in overwrite mode writes I over A, and both pointers step forward to B, so B is now the oldest and I the newest. The count stays at DEPTH and full stays high.

Dropping data silently is a trap. If software reads a trace buffer and does not know entries were lost, it will treat the oldest entry it sees as the start of the history. The sticky lost flag fixes that cheaply. A drop counter is the richer version: it tells software how much history is missing, and saturating it at its maximum value is usually enough.

Hand-drawn timing diagram of a four-entry ring in overwrite mode: pushes of A to D fill it, pushes of E and F overwrite A and B so the oldest entry moves to B and then C, the lost flag rises and stays high until clr_lost clears it.

The timing diagram runs six pushes into a four-entry ring in overwrite mode. After A to D it is full. E evicts A and sets lost, F evicts B, and the ring now holds C to F, the newest four. lost stays high until software pulses clr_lost.

RTL sketch

A power-of-two ring with the wrap bit from Part 1, an overwrite mode, a sticky lost flag, a registered read and a combinational peek:

module circ_fifo #(
  parameter int W     = 32,
  parameter int DEPTH = 16,               // power of two
  localparam int AW   = $clog2(DEPTH)
) (
  input  logic          clk,
  input  logic          rst_n,
  input  logic          overwrite,        // 1: drop oldest when full
  input  logic          push,
  input  logic [W-1:0]  wdata,
  output logic          full,
  input  logic          pop,
  output logic [W-1:0]  rdata,
  output logic          empty,
  output logic          lost,             // sticky: an entry was dropped
  input  logic          clr_lost,
  input  logic [AW-1:0] peek_off,         // 0 is the oldest entry
  output logic [W-1:0]  peek_data
);
  logic [W-1:0] mem [DEPTH];
  logic [AW:0]  wptr, rptr;

  assign empty = (wptr == rptr);
  assign full  = (wptr[AW-1:0] == rptr[AW-1:0]) && (wptr[AW] != rptr[AW]);

  wire do_pop  = pop && !empty;
  wire do_push = push && (!full || do_pop || overwrite);
  wire evict   = overwrite && push && full && !do_pop;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      wptr <= '0;
      rptr <= '0;
      lost <= 1'b0;
    end else begin
      if (do_push)         wptr <= wptr + 1'b1;
      if (do_pop || evict) rptr <= rptr + 1'b1;
      lost <= evict || (lost && !clr_lost);
    end

  always_ff @(posedge clk) begin
    if (do_push) mem[wptr[AW-1:0]] <= wdata;
    if (do_pop)  rdata <= mem[rptr[AW-1:0]];
  end

  assign peek_data = mem[AW'(rptr + peek_off)];
endmodule

The eviction reuses the pop's pointer increment, so overwrite mode costs one gate on the push accept and one on the read pointer enable. If clr_lost and an eviction happen in the same cycle, the eviction wins, so software can never clear away a drop it has not seen. A counter that software reads and subtracts is the alternative when it needs to know how many entries were lost.

Corner cases

  • Peek beyond the count. peek_off at or above the number of stored entries returns stale data. Either compare against the count and return a valid bit, or document that software must check the count first.
  • Peek during an eviction. The entry at offset 0 changes identity when the oldest is evicted. A trace readout should freeze the buffer (stop pushes) before reading it, or tolerate a moving window.
  • Switching modes when full. Turning overwrite off while the ring is full simply makes the next push wait. Turning it on lets the next push evict. Neither breaks the pointers.
  • Both pointers wrapping together. An eviction or a push and pop at the last slot wraps both pointers in one cycle. Their wrap bits flip together and the full flag holds.
  • DEPTH of 2. Every eviction and every boundary case happens every other cycle, which makes a small depth the most effective regression setting.

Timing, area and power

  • Accept path. do_push gains an OR term with overwrite, which is static, so it adds almost nothing.
  • Peek port. A second DEPTH-to-1 read mux with an adder on its select. For a debug port that is read rarely, a registered peek with a cycle of latency is fine and much cheaper in timing.
  • Area. The lost flag is one flop; a drop counter is a few more. The peek mux is the main addition.
  • Power. In overwrite mode a trace buffer writes every cycle the source is active, so the storage is always toggling. Gate the source, not the buffer, when tracing is off.

Verification checklist

  • A reference ring that, in overwrite mode, drops its oldest entry on a push when full, and in normal mode refuses it. Check every pop, every peek inside the count, full, empty and lost each cycle.
  • Assertions:
    a_no_ovf:  assert property (@(posedge clk) disable iff (!rst_n)
                 !overwrite |-> !(push && full && !pop));
    a_evict:   assert property (@(posedge clk) disable iff (!rst_n)
                 overwrite && push && full && !pop |=> full && lost);
    a_flags:   assert property (@(posedge clk) disable iff (!rst_n)
                 !(full && empty));
  • Coverage of each of the four full-boundary cases in each mode, at every slot index, plus evictions back to back, clr_lost with and without a same-cycle eviction, and a mode change while full.
  • Long runs so that both pointers wrap many times, with the traffic mix changing between push-heavy and pop-heavy.

Interview questions

1. The buffer is full and a push and a pop arrive together. What happens?

A strong answer says both are accepted on the same slot, explains why a registered read returns the old, correct entry, and raises the memory read-during-write question.

2. How do you make a trace buffer that never stalls the source?

A strong answer adds an overwrite mode that evicts the oldest entry on a push when full, advancing both pointers, and adds a lost flag or drop counter so software knows history was dropped.

3. How would software read the last 16 entries without disturbing the buffer?

A strong answer describes a peek port at rptr + offset, a freeze of the source during readout, and a count check for offsets beyond the stored entries.

4. Clear and eviction land in the same cycle. Which wins?

A strong answer picks one on purpose, usually the eviction so no drop is missed, and explains the software race either way.

5. What is different about verifying overwrite mode?

A strong answer says the reference model must drop the oldest entry too, and the coverage must include evictions at every slot and mode changes while full.

Where it is used in real chips

Circular buffers with overwrite are standard in on-chip trace and debug logic for processors and interconnects, in event and error logs inside power, security and reliability controllers, in sample history buffers for sensors and analog front ends, and in performance monitoring. The lossless mode is the ordinary FIFO found in DMA engines, AXI and PCIe interfaces, and network-on-chip routers.

The rest of the series

Part 8 covered the non-power-of-two FIFO, with explicit wraparound, phase bits and exact capacity.

Part 10 is the elastic FIFO: backpressure, skid buffers and full throughput between pipeline stages.

Share Facebook X LinkedIn WhatsApp Email

Post a Comment

0 Comments

Your comments will be moderated before it appears here.

Post a Comment (0)

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!