Change Details

The computations of vm_map_splay_split and vm_map_splay_merge touch both children of every entry on the search path as part of updating values of the max_free field. By comparing the max_free values of an entry and its child on the search path, we can avoid accessing the child off the path in cases where the max_free value decreases along the path. However, this requires that the vm_map structure begins in a consistent state. A recent change (r345702) added consistency checks on exit from the link, unlink, splay, findspace and resize_free operations, but those conditions are not checked on entry to those functions, and they may not hold. In particular, the clip_start and clip_end operations alter start or end fields, invalidating map consistency before invoking a link operation to fix things. This patch makes clipping a part of the link operation to avoid this inconsistency. Also several resize_free operations are preceded by changes to an entry end. This patch makes changing that value part of the resize_free operation. With all changes that change the size of free zones limited to these few functions, the map invariants hold on entry to these map functions, and it's safe to make inferences about max_free values to avoid accessing so many map entries. Tested by: pho

The computations of vm_map_splay_split and vm_map_splay_merge touch both children of every entry on the search path as part of updating values of the max_free field. By comparing the max_free values of an entry and its child on the search path, we can avoid accessing the child off the path in cases where the max_free value decreases along the path. Specifically, this patch changes splay_split so that the max_free field of every entry on the search path is replaced, temporarily, by the max_free field from its child not on the search path or, if the child in that direction is NULL, then a difference between start and end values of two pointers already available in the split code, without following any next or prev pointers. However, to find that max_free value does not require looking toward that other child if either the child on the search path has a lower max_free value, or the current max_free value is zero, because in either case we know that the value of max_free for the other child is the value we already have. So, the changes to vm_entry_splay_split make sure that we know all the off-search-path entries we will need to complete the splay, without looking at all of them. There is an exception at the bottom of the search path where we cannot rely on the max_free value in the direction of the NULL pointer that ends the search, because of the behavior of entry-clipping code. The corresponding change to vm_splay_entry_merge makes it simpler, since it's just reversing pointers and updating running maxima. Tested by: pho

The computations of vm_map_splay_split and vm_map_splay_merge touch both children of every entry on the search path as part of updating values of the max_free field. By comparing the max_free values of an entry and its child on the search path, we can avoid accessing the child off the path in cases where the max_free value decreases along the path. HoweverSpecifically, this requirespatch changes splay_split so that the vm_map structure begins in a consistent state.max_free field of every entry on the search path is replaced, A recent change (r345702) added consistency checks on exit from the linktemporarily, unlinkby the max_free field from its child not on the search path or, splayif the child in that direction is NULL, findspace and resize_free operationsthen a difference between start and end values of two pointers already available in the split code, but those conditions are not checked on entry to those functionswithout following any next or prev pointers. However, and they may not hold.to find that max_free value does not require looking toward that other child if either the child on the search path has a lower max_free value, In particularor the current max_free value is zero, the clip_start and clip_end operations alter start or end fieldsbecause in either case we know that the value of max_free for the other child is the value we already have. So, invalidating map consistency before invoking a link operationthe changes to vm_entry_splay_split make sure that we know all the off-search-path entries we will need to fix things.complete the splay, This patch makes clipping a part of the link operation to avoid this inconsistencywithout looking at all of them. Also several resize_free operations are preceded by changes to an entry end.There is an exception at the bottom of the search path where we cannot rely on the max_free value in the direction of the NULL pointer that ends the search, This patch makes changing that value partbecause of the behavior of the resize_free operationentry-clipping code. With all changes that change the size of free zones limited to these few functions, the map invariants hold on entry to these map functionsThe corresponding change to vm_splay_entry_merge makes it simpler, andsince it's safe to make inferences about max_free values to avoid accessjust reversing pointers and updating so many map entriesrunning maxima. Tested by: pho