LF OS
Hobby operating system for amd64 with high ambitions
Loading...
Searching...
No Matches
tpa.c File Reference

(29312b1 fbconsole, panic: render panic after framebuffer was given to userspace - without clearing screen contents)

#include <tpa.h>
#include <stdbool.h>
#include <string.h>
+ Include dependency graph for tpa.c:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  tpa_page_header
 Header of a tpa page. Data follows after this until &tpa_page_header+tpa->page_size. More...
 
struct  tpa
 Header of a TPA. More...
 

Functions

tpa_ttpa_new (allocator_t *alloc, uint64_t entry_size, uint64_t page_size, tpa_t *tpa)
 
void tpa_delete (tpa_t *tpa)
 
size_t tpa_size (tpa_t *tpa)
 
size_t tpa_entries_per_page (tpa_t *tpa)
 
ssize_t tpa_length (tpa_t *tpa)
 
uint64_t tpa_offset_in_page (tpa_t *tpa, uint64_t idx)
 
uint64_ttpa_get_marker (tpa_t *tpa, struct tpa_page_header *page, uint64_t idx)
 
bool tpa_entry_exists_in_page (tpa_t *tpa, struct tpa_page_header *page, uint64_t idx)
 
size_t tpa_entries (tpa_t *tpa)
 
struct tpa_page_headertpa_get_page_for_idx (tpa_t *tpa, uint64_t idx)
 
void * tpa_get (tpa_t *tpa, uint64_t idx)
 
void tpa_clean_page (tpa_t *tpa, struct tpa_page_header *page)
 
void tpa_set (tpa_t *tpa, uint64_t idx, void *data)
 
size_t tpa_next (tpa_t *tpa, size_t cur)
 

Detailed Description

This file and tpa.h are the implementation of a thin provisioned array, an array with unlimited size and holes for unused data.

There is a small data overhead (8 byte per entry, could be 4 byte on 32bit platforms. aligned) and quite some important runtime overhead (linked list to find the correct page, array access in page).

However, the implementation is simple and for many use cases this is a practical thing :)

You can look at /t/kernel/tpa.c for some examples.

License: MIT Author: Mara Sophie Grosch (littl.nosp@m.efox.nosp@m.@lf-n.nosp@m.et.o.nosp@m.rg)

Definition in file tpa.c.


Data Structure Documentation

◆ tpa_page_header

struct tpa_page_header

Header of a tpa page. Data follows after this until &tpa_page_header+tpa->page_size.

Definition at line 24 of file tpa.c.

+ Collaboration diagram for tpa_page_header:
Data Fields
struct tpa_page_header * next Pointer to the next page.
struct tpa_page_header * prev
uint64_t start_idx First index in this page.

◆ tpa

struct tpa

Header of a TPA.

Definition at line 34 of file tpa.c.

+ Collaboration diagram for tpa:
Data Fields
allocator_t * allocator Allocator for new tpa pages.
uint64_t entry_size Size of each entry.
struct tpa_page_header * first Pointer to the first data page.
uint64_t page_size Size of each data page.

Function Documentation

◆ tpa_clean_page()

void tpa_clean_page ( tpa_t tpa,
struct tpa_page_header page 
)

Definition at line 156 of file tpa.c.

References tpa::allocator, allocator::dealloc, tpa::first, tpa_page_header::next, tpa_page_header::prev, tpa_entries_per_page(), and tpa_entry_exists_in_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_delete()

void tpa_delete ( tpa_t tpa)

Deallocate every data in use by the given TPA And the TPA itself

Parameters
tpaThe TPA to destroy

Definition at line 61 of file tpa.c.

References tpa::allocator, allocator::dealloc, tpa::first, and tpa_page_header::next.

+ Here is the caller graph for this function:

◆ tpa_entries()

size_t tpa_entries ( tpa_t tpa)

Counts the number of existing entries in the TPA

Remarks
Has to search through the TPA and might be slow
Parameters
tpaThe TPA
Returns
The number of entries currently set in the TPA

Definition at line 110 of file tpa.c.

References tpa::first, tpa_page_header::next, tpa_entries_per_page(), and tpa_entry_exists_in_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_entries_per_page()

size_t tpa_entries_per_page ( tpa_t tpa)

Definition at line 83 of file tpa.c.

References tpa::entry_size, and tpa::page_size.

+ Here is the caller graph for this function:

◆ tpa_entry_exists_in_page()

bool tpa_entry_exists_in_page ( tpa_t tpa,
struct tpa_page_header page,
uint64_t  idx 
)

Definition at line 106 of file tpa.c.

References tpa_get_marker().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_get()

void * tpa_get ( tpa_t tpa,
size_t  idx 
)

Retrieve a given element from the TPA or NULL if the element is not present

Parameters
tpaThe TPA
idxThe index of the element to retrieve
Returns
pointer to the first byte of the entry

Definition at line 144 of file tpa.c.

References tpa_page_header::start_idx, tpa_entry_exists_in_page(), tpa_get_page_for_idx(), and tpa_offset_in_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_get_marker()

uint64_t * tpa_get_marker ( tpa_t tpa,
struct tpa_page_header page,
uint64_t  idx 
)

Definition at line 102 of file tpa.c.

References tpa_offset_in_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_get_page_for_idx()

struct tpa_page_header * tpa_get_page_for_idx ( tpa_t tpa,
uint64_t  idx 
)

Definition at line 127 of file tpa.c.

References tpa::first, tpa_page_header::next, tpa_page_header::start_idx, and tpa_entries_per_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_length()

ssize_t tpa_length ( tpa_t tpa)

Retrieve the highest index currently possible without new allocation

Remarks
Has to search through the TPA and might be slow
Parameters
tpaThe TPA
Returns
The index after the last entry in the last allocated page or -1

Definition at line 87 of file tpa.c.

References tpa::first, tpa_page_header::next, tpa_page_header::start_idx, and tpa_entries_per_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_new()

tpa_t * tpa_new ( allocator_t alloc,
uint64_t  entry_size,
uint64_t  page_size,
tpa_t tpa 
)

Allocate and initialize a new Thin Provisioned Array

Parameters
allocAllocator function to use
deallocDeallocator function to use
entry_sizeSize of each entry
page_sizeSize of each data page
tpaPointer to a memory region to use as tpa, 0 to alloc internally
Returns
A new TPA to use

Definition at line 48 of file tpa.c.

References allocator::alloc, alloc, tpa::allocator, tpa::entry_size, tpa::first, and tpa::page_size.

+ Here is the caller graph for this function:

◆ tpa_next()

size_t tpa_next ( tpa_t tpa,
size_t  cur 
)

Returns the next non-empty element after cur

Remarks
Has to iterate through the pages to get the page to the cur idx
Parameters
tpaThe TPA
curThe current index
Returns
The next non-empty element index after cur. Special case: returns 0 when nothing found, you are expected to check if the returned value is larger than cur to check if something was found.

Definition at line 223 of file tpa.c.

References tpa::first, tpa_page_header::next, tpa_page_header::start_idx, tpa_entries_per_page(), and tpa_get_marker().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_offset_in_page()

uint64_t tpa_offset_in_page ( tpa_t tpa,
uint64_t  idx 
)

Definition at line 98 of file tpa.c.

+ Here is the caller graph for this function:

◆ tpa_set()

void tpa_set ( tpa_t tpa,
size_t  idx,
void *  data 
)

Set new data at the given index

Remarks
This function might have to allocate a new page and could take some time to complete
Parameters
tpaThe TPA
idxWhere to place the new entry
dataPointer to the first byte of the data to store

Definition at line 174 of file tpa.c.

References allocator::alloc, tpa::allocator, tpa::entry_size, tpa::first, memcpy(), memset(), tpa_page_header::next, tpa::page_size, tpa_page_header::prev, tpa_page_header::start_idx, tpa_clean_page(), tpa_entries_per_page(), tpa_get_marker(), tpa_get_page_for_idx(), and tpa_offset_in_page().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ tpa_size()

size_t tpa_size ( tpa_t tpa)

Returns the allocated size of the TPA in bytes

Remarks
Has to search through the TPA and might be slow
Returns
The size of all pages combined of this TPA in bytes

Definition at line 72 of file tpa.c.

References tpa::first, tpa_page_header::next, and tpa::page_size.

+ Here is the caller graph for this function: