[patch 0/3] x86: Use interval tree to keep track of PAT reserve/free
in [Kernel]
|
Prev: [PATCH v3 1/6] net: tcp_header_len_th and tcp_option_len_th
Next: oom: select task from tasklist for mempolicy ooms
From: venkatesh.pallipadi on 10 Feb 2010 16:40 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 <venkatesh.pallipadi(a)intel.com> Signed-off-by: Suresh Siddha <suresh.b.siddha(a)intel.com> -- -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |