Skip to content

Memory usage optimization #17

Open
@axos88

Description

@axos88

Based on the discussion in #16:

I think the pointer in the Hole structure can be removed and calculated on the fly from (&this as usize) + this.size.

Any reason we are not doing that?

Activity

phil-opp

phil-opp commented on Aug 30, 2019

@phil-opp
Member

I don't think this will work. Consider https://os.phil-opp.com/kernel-heap/overview.svg: The size of the unused memory block is completely independent from the size of the used memory block afterwards.

Basically, the size field stores the size of the unused block, and the pointer implicitly stores the size of the unusable memory block that follows.

axos88

axos88 commented on Aug 30, 2019

@axos88
Author

This is only in case there is padding due to alignment requirements isn't it? I'll have to look it up how I solved this issue.

phil-opp

phil-opp commented on Aug 30, 2019

@phil-opp
Member

If you keep track of both used and unused chunks, you can use this approach. However, if you only keep track of unused chunks, there is no way to know where the next unused block begins without storing a pointer.

axos88

axos88 commented on Aug 30, 2019

@axos88
Author

Well you don't really care about used chunks, since they're not available. And whenever somebody claims to try to free up a chunk, the allocator gets both the address, and the layout of said chunk, and blindly obliges, creating a new chunk (or extends a previous or next one, if the freed up memory are neighbours another free chunk). This would mean that an incorrect call (freeing up nonclaimed space, or double frees) would create corrupt the heap and cause chaos, but that's already the case, isn't it?

phil-opp

phil-opp commented on Aug 31, 2019

@phil-opp
Member

This would mean that an incorrect call (freeing up nonclaimed space, or double frees) would create corrupt the heap and cause chaos, but that's already the case, isn't it?

Yes, it is. Even a deallocate call with a valid address can cause undefined behavior due to use-after-free.

Well you don't really care about used chunks, since they're not available.

Yes, that's why this crate only keeps unused blocks in the list. I just don't understand how we can remove the pointer in the list nodes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @phil-opp@axos88

        Issue actions

          Memory usage optimization · Issue #17 · rust-osdev/linked-list-allocator