LinuxMM:

[:NitinGupta:Nitin Gupta]

MailTo(nitingupta910 AT gmail DOT com)


Manages storage for variable sized data objects

It is designed especially for embedded devices.


BR This page describes the problem it tries to solve and its design details. BR BR Problem StatementBR Normally when you allocate arbitrary sized objects using kmalloc()/vmalloc() there is big space wastage due to internal fragmentation. So, if memory is at premium, tight storage is required for these variables sized data items which is what VStore does. This however comes at cost of some speed. BRBR How to use it?BR To store data:

vstore_write(objectID /* out */, data_to_store, len)

To restore this data:

vstore_read(objectID, buffer, len /* out */)

NOTE: In vstore_read(), make sure that buffer is big enough to store data assoc. with object 'ObjectID' - the 'len' (out) param will tell how much data was read into the buffer. Thus, to make sure that buffer size is always sufficient, either you know maximum size for objects stored (more common case) or you will have to track size of each object stored to provide buffer of right size. BRBR

Design Details


Design Goals

BR Each data item stored is split into multiple chunks (small contiguous physical space) and these chunks can then be spread across multiple physical pages. The Metadata associated with each chunk is stored in the beginning of chunk itself with necessary padding added to maintain alignment constraints.

Chunks can be one of three types:

Following gives metadata layout for each of these types of chunks:

Some jargon first:

M     = Metadata - size has to be n * ALIGN_BYTES
M(A)  = address relative to page start (PAGE_SHIFT - ALIGN_SHIFT bits)
M(S)  = size of chunk (same as M(A))
F     = flags (2 bits)
        F(1): last chunk
        F(2): next chunk in diff page
FP    = prev chunk's flags
FN    = next chunk's flags
PFN   = PageFrameNo where next chunk exists (BITS_PER_LONG - PAGE_SHIFT bits)
OD(i) = i-th optional metadata field. Optional fields are enclosed on []

- Free chunk

M(A) | F | M(S) | free space

- Busy chunk type-1 (next chunk in same page)

M(A) | F | M(S) | [ M(S) of prev chunk ]
        - OD(1) exists if F(2) is not set

- Busy chunk type-2 (next chunk in different page)

M(A) | F | PFN | [ M(S) of prev chunk ] | [ M(S) of this chunk ]
        - only OD(1) exists if          FP(2) && !F(1)
        - only OD(2) exists if          F(1) && !FP(2)
        - both OD(1) and OD(2) exist if FP(2) && F(1)

NOTE: * Space is not reserved for optional fields that do not exist. Flags let us know which fields really exist. * Each type of chunk has required padding at end of metadata to satify alignment constraint.

LinuxMM: VStore (last edited 2007-07-24 15:19:14 by little-black-box)