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

Leave a Comment:

Your comment will be visible after approval.

(will not be published)