On Tue, Aug 7, 2018 at 6:28 AM, Waldek Kozaczuk <[email protected]> wrote:
> I am planning to take a stab at fixing https://github.com/cloudius- > systems/osv/issues/884. As explained in the issue, possible solution > would require data structure supporting efficient read from and write to > the file as well as memory allocation. > Yes, that is probably the best long-term solution, although as I suggested in the issue itself, a very simple hack which solves most of the problem (the quadratic complexity) is to grow the file by a fixed percentage every time. So it depends how quickly vs nicely you want to solve this problem. > One candidate is std::deque. Another structure fitting a bill is > std::unordered_map, which could store file segments of constant size (page > 4K or maybe bigger but power of 2). > You can also have an std::deque of pages instead of individual bytes, I think this will solve most of the issues you mention and I think would be the best solution. You can allocate pages with memory::alloc_page() or malloc(mmu::page_size) - both should be more-or-less equally efficient (malloc(page_size) doesn't waste additional memory). std::unordered_map seems to me excessive - if it's not very important for us to support files with huge holes. > Then for every write we would simply allocate missing file segments, for > reads we would simply find range of segments to copy from. The segments > would be keyed by (offset / segment size) and ideally page aligned. > > This data structure would support sparse file and help with addressing > issue https://github.com/cloudius-systems/osv/issues/979 to optimize > memory usage when mmap()-ing ramfs files. > > I wonder what others think about this approach. > > Waldek > > -- > You received this message because you are subscribed to the Google Groups > "OSv Development" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "OSv Development" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
