0
$\begingroup$

I am going to story data in a growable persistent storage. I need to implement allocation/deallocation (like malloc/free and possibly realloc but in Rust) of continuous regions of memory on this storage.

Allocation should never fail, but the storage grow if out of allocated storage.

Priorities:

  • Should do alloc/dealloc quick (i.e. desirably logarithm time of data size). That is the most important priority.
  • Prefer not to grow the persistent storage if possible (because the persistent storage price is proportional to its size).

Please describe a data structure holding allocated and free regions of memory an algorithm matching the requirements.

I am writing this in Rust. If this helps, I write/read persistent storage by one word, so reading/writing are relatively slow operations.

As a bonus, if not too hard to implement, I would like also abillity of splitting long regions of allocated storage into blocks (as in fragmented filesystems).

$\endgroup$
8
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – D.W.
    Mar 7, 2023 at 8:19
  • 2
    $\begingroup$ "as in fragmented filesystems" There's a clue right there. It sounds an awful lot like what you want to implement is kind of like a filesystem. Of course, filesystems don't necessarily store contiguous files in contiguous disk blocks. Is that a requirement? $\endgroup$
    – Pseudonym
    Mar 7, 2023 at 9:57
  • $\begingroup$ @Pseudonym For simplicity it could be implemented without fragmentation. But adding fragmentation may be useful. $\endgroup$
    – porton
    Mar 7, 2023 at 18:31
  • $\begingroup$ @D.W. Wikipedia misses a description of the data structure used to track allocated memory. I need a description of such a data structure. $\endgroup$
    – porton
    Mar 7, 2023 at 18:51
  • $\begingroup$ I've found github.com/microsoft/mimalloc - it remains to translate it to Rust and use input/output instructions instead of direct memory access. $\endgroup$
    – porton
    Mar 7, 2023 at 19:05

1 Answer 1

0
$\begingroup$

There is this Rust allocator described as "blazingly fast".

It remains to rewrite it with I/O functions instead of direct memory access.

$\endgroup$
2
  • $\begingroup$ That's a pool allocator. It would be very easy to implement that on disk, however it doesn't support deallocating individual objects. en.wikipedia.org/wiki/Memory_pool $\endgroup$
    – Pseudonym
    Mar 7, 2023 at 22:40
  • $\begingroup$ @Pseudonym I've also noticed this. Therefore, should I delete my answer? $\endgroup$
    – porton
    Mar 8, 2023 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.