search

gem5 / gem5

The official repository for the gem5 computer-system architecture simulator.
http://www.gem5.org
BSD 3-Clause "New" or "Revised" License
1.6k stars 1.18k forks source link

Making the implementation of mmap/munmap/mremap/fixupFault more time-efficient #1468

Open FJShen opened 1 month ago

FJShen commented 1 month ago

The time complexity of several methods in SE mode related to virtual memory page management is currently O(n), where n is the amount of pages. This is because gem5 keeps track of all currently mapped virtual memory pages in a simple linked list std::list<VMA> gem5::MemState::_vmaList, so whenever gem5 needs to find a page, it needs to linearly iterate over all VMA objects in the linked list. This operation is O(n) in time complexity and can happen in system calls including mmap, munmap and mremap. (It also happens when MemState::fixupFault is called for page faults in SE mode.) Therefore, for executables that map plenty of memory pages, the total overhead is unbearable (O(nn)).

I have worked out a solution to bring the time complexity down to O(logn) for this operation. The changes are confined to just a few files and are minimally disruptive. Would the community be interested in reviewing a PR for this fix?

powerjg commented 1 month ago

Thanks for creating this issue, @FJShen!

To answer your question, when I'm reviewing code I think about two main things:

  1. What is the impact of the change? In this case, how much performance improvement would we see from the change?
  2. How much more difficult (or easier) will the code be to maintain over the next 10+ year?

If the impact is small, then it's required that the maintenance burden doesn't increase.

Feel free to push your change and we can review it!

FJShen commented 1 month ago

Sounds good. I'm running unit tests right now, and I will create a PR once things are ready. In terms of impact, I'd say it really depends on the workload :D In my case, I am executing an ELFie that maps ~1.6GB of 4k pages. The changes shaved off tens of minutes from the simulation.

powerjg commented 1 month ago

10s of minutes seems worth it!

Please make the PR and we can have more discussion there.