Skip to content

x86: Use interval tree to keep track of PAT reserve/free

[email protected] lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest3 patches 6 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/3rbtree: Add support for augmented rbtreesDocumentation/rbtree.txt include/linux/rbtree.h lib/rbtree.c+67 -520 replies
2/3x86: Preparatory changes in pat.c for bigger rbtree changearch/x86/mm/pat.c arch/x86/mm/pat_internal.h+116 -821 reply
3/3x86: Migrate to rbtree only backend for pat memtype managementarch/x86/mm/Makefile arch/x86/mm/pat.c arch/x86/mm/pat_internal.h +1 more+294 -2052 replies

Reviews trailers per patch

1 of 3 patches has a Reviewed-by or Acked-by.

PatchVenkatesh PallipadiSuresh SiddhaAli Gholami Rudi
1/3A-b A-b A-b A-b A-b A-b T-b
2/3
3/3

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes. Scroll the table sideways for all 3 reviewers.

Read the v1 thread

Cover letter [patch 0/3] x86: Use interval tree to keep track of PAT reserve/free

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.