YAMM – Yet Another Memory Manager

Ionut Tolea and Andrei Vintila presented the paper Yet Another Memory Manager (YAMM) at SNUG Conference 2016 – Munich. The code of YAMM library is released to the public using AMIQ’s GitHub repository.


YAMM Overview

Yet Another Memory Manager (YAMM) is a SystemVerilog library that provides support for memory based operations:

  • Buffers can be allocated following 6 allocation modes with any granularity or address alignment
  • Buffers can be inserted by user (non-overlapping)
  • Buffers can be deallocated either by address or by handle
  • Buffers can be searched for in the memory space by address or by handle
  • Buffers support payload, which can be assigned by the user, randomly generated, read and compared.
  • Implements a fast buffer search algorithm

Beside these features YAMM provides debug facilities (e.g. memory map dump, usage statistics) and it is easy to integrate it with existing verification environments.


Basic Concepts

A memory map’s space is identified by a start address and a size. Similarly, a buffer is a continuous address space defined by a start address and a size. There are two types of buffers:

  • free buffer: can be used for further allocation/insertion of user buffers
  • user buffer: user allocated space

The memory map is initialized to a free buffer. To use a specific area in the memory you must allocate a buffer with a non-0 size. By allocating buffers in the memory, the initial free buffer is split and resized to make room for the new buffers as the example below shows.

Allocation example

De-allocation of a buffer is the inverse operation of allocation. De-allocation replaces a user buffer with a free buffer; YAMM checks if there are neighboring free buffers and merges them into a single free buffer to minimize the list of free buffers.

YAMM provides two classes which enable the memory management functionality:

  • yamm_buffer: base class that implements buffer specific features
  • yamm: inherits yamm_buffer and implements the memory map specific features

Structurally YAMM handles the memory map as a chain of free and occupied buffers managed as two double linked lists (see picture below):

  • all buffers list: chains all buffers in memory
  • free buffers list: chains only the free buffers
YAMM Double Linked Lists


Usage Examples

The following sections will present YAMM’s API through examples in order to get a basic understanding of the YAMM capabilities. Also, as a new user you should have a look at the yamm_tutorial.sv example.

Initialization

Define a memory map by instantiating the yamm object and calling the build() function. At this stage the memory has a name and a size and contains one free buffer that stretches the whole memory space.

import yamm_pkg::*;

// Instantiate a memory map
automatic yamm mem = new; 
// Initialize the memory map space to 1MByte and set it's name to YAMM_MEMORY_MAP
mem.build("YAMM_MEMORY_MAP", 1024*1024);

Buffer Operations: Insertion, Allocation, De-allocation

After initialization, buffers can be allocated by using one of the allocation methods (allocate(), allocate_by_size()). The memory manager will search for an appropriate free buffer to hold the desired memory space (i.e. the size of the free buffer is big enough to hold the allocated buffer). The search for a free buffer will take into account the allocation mode:

  • RANDOM_FIT – Random free buffer that fits the requested memory space, picks a random address inside the free buffer
  • FIRST_FIT – First free buffer that fits the requested memory space, picks first address inside the free buffer
  • BEST_FIT – Smallest free buffer that fits the requested memory space, picks first address inside the free buffer
  • UNIFORM_FIT – Biggest free buffer that fits the requested memory space, fits the allocated buffer in the middle of the free space
  • FIRST_FIT_RANDOM – First free buffer that fits the requested memory space, picks random address inside the free buffer
  • BEST_FIT_RANDOM – Smallest free buffer that fits the requested memory space, picks random address inside the free buffer

All allocation methods return an indication if the allocation was successful or not. In case of successful allocation they return a pointer towards the buffer or a 1’b1, otherwise they return a null buffer or a 1’b0, depending on the method being used.
In the code box below you can see a couple of examples on buffer allocation:

  // declare a yamm_buffer variable
  yamm_buffer a_buffer = new;
  a_buffer.size = 256;
  assert(mem.allocate(a_buffer, RANDOM_FIT)) else `uvm_warning("APB_SEQ", "Can not insert the desired buffer!");
  a_buffer.set_name("A_Buffer");

  ........................
  // allocate by size
  yamm_buffer x_buffer = mem.allocate_by_size(256, RANDOM_FIT);
  assert(x_buffer != null) else `uvm_error("APB_SEQ", "Can not insert the desired buffer!");
  x_buffer.set_name("X_Buffer");

Buffers can also be “manually” inserted at a specific address by using one of the insert methods (e.g. insert(), insert_by_access()). In this case the memory manager will only check if there is enough space at the given address and do the buffer insert.

  yamm_buffer a_buffer = new;
  a_buffer.set_name("A_Buffer");
  a_buffer.size = 256;
  a_buffer.start_addr = 'hCAFE1001;
  // insert() function returns 1 if the insert is successful
  assert (!mem.insert(a_buffer)) else `uvm_warning("APB_SEQ", "Can not insert the desired buffer!");

You probably noticed that buffers get a type name through the set_name() call. Although this operation is not mandatory, it can be helpful if you need to search buffers by type.

The verification components should deallocate buffers as soon as they stop being used. This can be achieved by calling deallocate() for a buffer or deallocate_by_addr() for an address.

  // deallocate by buffer
  mem.deallocate(a_buffer);
  ..............................

  // deallocate by address 
  mem.deallocate_by_addr('hCAFE1001);

Once a buffer is allocated by a verification component it can be searched and used for various purposes (e.g. configuration, checking, payload retrieval) by other verification components. YAMM provides a search API that accepts as search criteria an address, an address range (or an access) or a buffer type. Depending on the search operation a buffer or a list of buffers will be returned; if the search is unsuccessful a null buffer or an empty list will be returned.

   // search buffer by address
   yamm_buffer a_buffer = mem.get_buffer('hCAFE1001);

   ..............................
   // search buffers by address range or by access
   yamm_access basic_access = new;
   basic_access.start_addr = 0;
   basic_access.size = mem.size/2;
   // Get all the buffers contained in the first half of the memory
   yamm_buffer queue[$] = mem.get_buffers_by_access(basic_access);

   ..............................
   // search buffers by range
   yamm_buffer queue[$] = mem.get_buffers_in_range(0, mem.size/2);

   ..............................
   // search buffers by type
   yamm_buffer queue[$] = mem.get_all_buffers_by_type("a_buffer");

Buffer Content Operations

Class yamm_buffer provides API to handle buffer’s contents or payload (i.e. a list of bytes). The user can overwrite the generate_contents() method to generate specific buffer contents. User can directly set buffer’s contents by calling set_contents() or retrieve buffer’s contents by calling get_contents().
The code box below shows few examples of using contents API:

   // set buffer's content
   a_buffer.set_contents('{‘h54,’h45,’h53,’h54});
   ...................................

   // generate buffer's content
   a_buffer.generate_contents();
   ...................................

   // retrieve buffer's content
   byte contents[] = a_buffer.get_contents();

   ...................................
   // Compare buffer's contents to a list of bytes
   assert (general_buffer.compare_contents(access.payload)) else `uvm_error("APC_SCBD", "Contents is not what I expect!");

If the method get_contents() is called without previous initialization of buffer’s contents, it will automatically call the generate_contents() method.


Comparison with uvm_mam

UVM provides a memory model that comes with a simple memory manager called uvm_mam (see Memory Allocation Manager). We used uvm_mam as a reference for feature and performance comparison purposes.

Feature-Wise Comparison
# Category MAM YAMM
1 Memory uvm_mam is linked to uvm_mem which provides the memory locations used for storing data The YAMM top level, as well as every individual buffer contains a memory map composed of multiple buffers that can store simple data
2 Allocation Can only allocate on previously unallocated memory and has only 2 allocation modes Permits allocation in previously allocated memory or inside an already allocated buffer and has 6 allocation modes
3 Deallocation Releases the specific region Releases the region and can display a warning if the deallocated buffer contains other buffers
4 Finding buffers Provides an iterator that user has to use for any needs Provides support for finding and modifying buffers by different criteria
5 Ease of use It’s complex and rather hard to use and for features beyond reserving and freeing regions the user has to go to objects higher in the hierarchy Everything is provided in the same package and can be easily accessed. Memory map can be accessed by calling functions on the top level. Specific regions can be accessed by calling the same functions on the chosen buffers

We measured the performance using the following scenario:

  • Memory space of 1GB
  • 5000 buffer allocations of size 100Bytes
  • Measured the time taken for every 100 allocations
  • Used the broad policy for MAM’s request_region()
  • Used the RANDOM_FIT allocation mode for YAMM’s allocate_by_size()

After running the performance test I obtained the following statistics graphs.

MAM performance graph


YAMM performance graph

The measurements show that allocation of 5000 buffers takes 2 seconds for YAMM compared to MAM which takes 525 seconds. Also the curve that dictates the time dependency with increasing number of allocations is linear in case of YAMM and exponential in case of MAM.

Resources

The YAMM code is provided as an opensource library under Apache License 2.0.
You can download the YAMM library from GitHub.
For getting up to speed you can download YAMM’s User Manual or browse the HTML documentation.

Roadmap

YAMM library is ready to be used for SystemVerilog/UVM-based verification right away. Our roadmap includes few items:

  • Release the C/C++ version
  • Release the e-language version
  • Port the existing SystemVerilog tests to UVM/SV or SVUnit tests
  • Implement access policies

For information on YAMM releases and bug fixes, follow AMIQ’s blog or GitHub repository.


Comments

elihai February 10th, 2020 14:52:46

hello!
great pkg for memory allocation. helps a lot.
I think i saw a bug in the allocate_by_size func:

function yamm_buffer yamm_buffer::allocate_by_size(yamm_size_width_t size, yamm_allocation_mode_e allocation_mode = RANDOM_FIT);

// Create a buffer and give it the specified size
yamm_buffer new_buffer = new;
new_buffer.size = size;

// Allocate it using the allocation function
if(this.allocate(new_buffer, allocation_mode)) begin
return new_buffer;
end

It doesn’t copy also the configured granularity/start_addr_align, so I get an irrelevant address.

a quick fix:

new_buffer.size = size;
new_buffer.set_granularity(this.get_granularity);
new_buffer.set_start_addr_alignment(this.get_start_addr_alignment);

what do you say?


Andrei Vintila February 18th, 2020 11:09:14

Hello Elihai,

Firstly, sorry for such a late response.

You are correct, there is no way at the moment to use the allocate_by_size() function with different granularities. Conceptually speaking, we don’t want to force the granularity of the above layer of buffers on the sub-buffers. That can be already be done by using allocate() or insert() of buffers created by you. Any granularity can be used.

I can have a talk with some other users and eventually, i can provide a new argument to the function that would incorporate the functionality you suggested (e. g. port the same granularity as the buffer on the layer above). At the moment my idea would be to keep the default functionality “as is”, but if nobody objects, i can also change it permanently the way you suggested.

I can get back to you once the git version was updated.

Cheers!

Andrei


Elihai March 19th, 2020 09:44:54

thanks for your response!
the fixed that i offered works well for me..

another issue i’ve found, is that when i use allocate_by_size, the given buffer is not in: start_addr-end_addr range, but in: 0:size range.
is this in purpose?

code:


module yamm_tb();
  yamm        m_memory_manager[3];

  initial begin
    foreach (m_memory_manager[ii]) begin
      m_memory_manager[ii] = new();
    end
    
    m_memory_manager[0].build("system memory", 16*1024*1024);
    m_memory_manager[0].set_granularity(4);
    m_memory_manager[0].set_start_addr(32'h1000_0000);

    //...

    foreach (m_memory_manager[ii]) begin
      m_memory_manager[ii].reset();
    end

    $display("mem[0]");
    repeat (10) begin
      m_buff = m_memory_manager[0].allocate_by_size(512);
      $display("addr := 0x%08h", m_buff.get_start_addr);

    end
  
    //...

    $finish();
  end
endmodule

results:
mem[0]
addr := 0x00815e8c
addr := 0x00415fec
addr := 0x00c15d24
addr := 0x0061b718
addr := 0x002108b8
addr := 0x003160b4
addr := 0x00294b24
addr := 0x0010b0b8
addr := 0x002d6100
addr := 0x00253540

    Andrei Vintila April 16th, 2020 13:37:58

    Hi Elihai,

    Sorry for the late reply, it’s been a difficult period.

    Unfortunately, you are correct, when building a memory, only the size and end address are taking in account. For our own projects we use our own interchangeable offsets when accessing different memories, especially since we also have other misc access rules. For this purpose, the offset for the created memories has been left as 0, to not conflict with user defined adaptation layers.

    Cheers!

    Andrei


Leave a Comment:

Your comment will be visible after approval.

(will not be published)

This site uses Akismet to reduce spam. Learn how your comment data is processed.