AIX51D: Dynamic Interval Management
Original Publication Date: 2002-Nov-24
Included in the Prior Art Database: 2003-Jun-21
Disclosed is a method for managing information describing discrete, non-contiguous intervals dynamically. Originally in AIX* there existed intervals to manage page replacement domains, describe memory holes, memory that should be freed after system initialization (SI) time, etc. These intervals were described in statically sized arrays and therefore were difficult to modify and could not be extended indefinitely. This is a problem with a Dynamic Reconfig (DR; a system that allows resources to be moved at runtime between logical partitions) system where it is unknown how many memory holes the system may have over its life. In addition, the page replacement domains need to be modified regularly as memory is added and removed. To solve this problem, a data structure and suite of operations is used. These operations allow the creation and management of descriptions of intervals of memory dynamically, that can be used for page replacement domains, memory holes, non-removable memory, etc. These dynamic intervals can grow essentially without limit and are easy to manipulate. The intervals are described as a doubly-linked list where each element in the list has a start, end pair describing one contiguous range of elements. The list has a dummy head and tail, and the dummy head maintains a count of the total number of pages covered by the list, and also has a per-list lock that can be used to serialize operations on the list. A suite of routines exists to create lists, add and remove contiguous ranges from a list, query whether a particular element is within an interval list, and whether another range intersects or is wholly contained in an interval list. Lists can be unioned and intersected.