Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Remove "impossilbe defrags" by concatenating in both directions #15

Open
jfrimmel opened this issue Aug 21, 2022 · 0 comments
Open

Remove "impossilbe defrags" by concatenating in both directions #15

jfrimmel opened this issue Aug 21, 2022 · 0 comments
Labels
algorithm Isses regarding the used algorithm

Comments

@jfrimmel
Copy link
Owner

The algorithm description of emballoc 0.1.1 mentions, that the concatenation of free blocks only happens with the following block and not the previous one (cf. step 12). I propose a simple solution, that will prevent such scenarios without the need for the mentioned linear scan.

The key idea is to write the Entry not only to the start of a block (as it is currently done as a header), but also into the block itself. If the block is written to the last four bytes of the memory, the length of the block is known. This in turn would allow to patch the header of that block with the length of the current block to be freed (and the following free block if there is such a block).
It also works with "empty" blocks: from the view of the following block, the previous 4 bytes are a valid header and one needs to jump 0 bytes to the left to access the "real" header (which is the same). This keeps the logic simple and straightforward.
There is no alignment issue, since an allocated block is always rounded up to a multiple of 4, so the entry can safely be written or read.

@jfrimmel jfrimmel added the algorithm Isses regarding the used algorithm label Aug 21, 2022
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
algorithm Isses regarding the used algorithm
Projects
None yet
Development

No branches or pull requests

1 participant