Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: <venkatesh.pallipadi <at> intel.com>
Subject: [patch 0/3] x86: Use interval tree to keep track of PAT reserve/free
Newsgroups: gmane.linux.kernel
Date: Wednesday 10th February 2010 19:57:04 UTC (over 6 years ago)
Reserve and free ranges of IO region has to be kept track of in x86 PAT, as
the same region should not be mapped with conflicting types by multiple
users.
These reserve and free requests can be of varying sizes and can overlap in
various ways. As in
uncached-minus @ 0xfbf00000-0xfbf04000
uncached-minus @ 0xfbf02000-0xfbf03000
or
uncached-minus @ 0xfbf00000-0xfbf04000
uncached-minus @ 0xfbf03000-0xfbf05000
etc.
depending on driver usage model.

And PAT code has to have efficient conflict lookup (while adding a new
region), exact region lookup (to free currently reserved region) and type
lookup (to lookup the memtype of any particular address).

Currently this is done by using a linked-list and rbtree hybrid model,
where linked list is sorted in increasing start address of these ranges.

But, the optimal way to deal with this is to use interval tree
(augmented rbtree). The patchset adds support for augmented rbtree in
generic rbtree code and uses that in x86 PAT, there by
cleaning up and simplifying the current PAT reserve-free backend.

Signed-off-by: Venkatesh Pallipadi 
Signed-off-by: Suresh Siddha 

--
 
CD: 23ms