Memory Type Based Allocation - Revision history

Prpplague at 21:14, 2 December 2009

2009-12-02T21:14:39Z

Wmat: /* Source Code */

2006-12-12T14:27:12Z

‎Source Code

Wmat: fixing links

2006-12-12T13:41:10Z

fixing links

Wmat: fixing links

2006-12-12T13:30:57Z

fixing links

Wmat at 19:12, 11 December 2006

2006-12-11T19:12:36Z

Wmat: /* Tracing MTA with Linux Trace Toolkit */

2006-12-11T19:09:05Z

‎Tracing MTA with Linux Trace Toolkit

Wmat: /* User API’s */

2006-12-11T19:08:49Z

‎User API’s

Wmat: /* Kernel API’s */

2006-12-11T19:07:35Z

‎Kernel API’s

Wmat: /* Allocating Pages With a Node List */

2006-12-11T19:06:17Z

‎Allocating Pages With a Node List

Wmat: /* Default Page Allocator */

2006-12-11T19:05:18Z

‎Default Page Allocator

@@ Line 11: / Line 11: @@
 == Feature Requirements ==
-#All of a program’s segments must be locatable in specified memory devices: text, initialized data (data), unitialized data (bss), heap (brk), and stack.
+#All of a program’s segments must be locatable in specified memory devices: text, initialized data (data), unitialized data (bss), [[Heap_memory|heap]] (brk), and stack.
 #The loadable segments of shared libraries (text and initialized data) must be locatable in specified memory devices.
 #The ELF binaries of programs and shared libraries must contain memory device information for each of the binaries’ loadable segments (text and initialized data). This must be in the form of mnemonic strings. For instance: "SRAM", "SDRAM", etc.
@@ Line 35: / Line 35: @@
 </pre>
-The memory type mnemonic strings specified to the tool are copied to a temporary file, and that file is passed to objcopy, which copies the temporary file’s contents to the new .memtypes section. Currently, the elfmemtypes tool allows specifying memory types for the text segment and data segment. The text segment includes code and read-only data sections, and therefore all these sections will be allocated to the memory types specified for text. Likewise, the data segment includes initialized data (data) and uninitialized data (bss), so all these sections will be allocated to the memory types specified for data. Also, although there are no heap (brk) and stack sections defined for ELF binaries, heap and stack regions for the new process currently use the memory types specified for data. A future enhancement will be to allow data, bss, brk, and stack regions to have their own memory types.  The command line arguments to the tool are as follows to mark an ELF binary:
+The memory type mnemonic strings specified to the tool are copied to a temporary file, and that file is passed to objcopy, which copies the temporary file’s contents to the new .memtypes section. Currently, the elfmemtypes tool allows specifying memory types for the text segment and data segment. The text segment includes code and read-only data sections, and therefore all these sections will be allocated to the memory types specified for text. Likewise, the data segment includes initialized data (data) and uninitialized data (bss), so all these sections will be allocated to the memory types specified for data. Also, although there are no [[Heap_memory|heap]] (brk) and stack sections defined for ELF binaries, [[Heap_memory|heap]] and stack regions for the new process currently use the memory types specified for data. A future enhancement will be to allow data, bss, brk, and stack regions to have their own memory types.  The command line arguments to the tool are as follows to mark an ELF binary:
 <pre>

← Older revision		Revision as of 14:27, 12 December 2006
Line 466:		Line 466:
	== Source Code ==		== Source Code ==
	[[linux-mta-041004.tar.bz2]] is a kernel soruce archive including MTA. Please someone isolate MTA funtion from the tarball. [[mta-utils.tar.gz MTA util]] and [[Media:mta-glibc-2.2.5.patch\|mta-glibc-2.2.5.patch]] are also available.		[[linux-mta-041004.tar.bz2]] is a kernel soruce archive including MTA. Please someone isolate MTA funtion from the tarball. [[mta-utils.tar.gz MTA util]] and [[Media:mta-glibc-2.2.5.patch\|mta-glibc-2.2.5.patch]] are also available.
		+
		+	[[Category:Memory Type Based Allocation]]

← Older revision		Revision as of 13:41, 12 December 2006
Line 465:		Line 465:

	== Source Code ==		== Source Code ==
−	[[linux-mta-041004.tar.bz2]] is a kernel soruce archive including MTA. Please someone isolate MTA funtion from the tarball. [[mta-utils.tar.gz MTA util]] and [[Media:mta-glibc-2.2.5.patch glibc patch]] are also available.	+	[[linux-mta-041004.tar.bz2]] is a kernel soruce archive including MTA. Please someone isolate MTA funtion from the tarball. [[mta-utils.tar.gz MTA util]] and [[Media:mta-glibc-2.2.5.patch\|mta-glibc-2.2.5.patch]] are also available.

← Older revision		Revision as of 13:30, 12 December 2006
Line 465:		Line 465:

	== Source Code ==		== Source Code ==
−	[[linux-mta-041004.tar.bz2]] is a kernel soruce archive including MTA. Please someone isolate MTA funtion from the tarball. [[mta-utils.tar.gz MTA util]] and [[mta-glibc-2.2.5.patch glibc patch]] are also available.	+	[[linux-mta-041004.tar.bz2]] is a kernel soruce archive including MTA. Please someone isolate MTA funtion from the tarball. [[mta-utils.tar.gz MTA util]] and [[Media:mta-glibc-2.2.5.patch glibc patch]] are also available.

@@ Line 85: / Line 85: @@
 text/data. The MTA config file syntax defines two keywords for these purposes.
-== define_node keyword ==
+=== define_node keyword ===
 To define nodes for configuring a kernel, use the following MTA config file line:
@@ Line 129: / Line 129: @@
 A macro in the generated header file called INSTANTIATE_MTA_NODES will instantiate the mta_nodes[] array. This is done in mm/numa.c in the kernel source.
-== tag_elf keyword ==
+=== tag_elf keyword ===
 The second use for the MTA config file is to mark ELF binaries in a target file system with memory type information. This is simply a convenience, it allows a file system’s memtypes configuration to be described in a single location, instead of having to invoke the elfmemtypes tool many times to configure the file system.
@@ Line 162: / Line 162: @@
 The script will call the elfmemtypes tool with the clear argument once for every tag_elf line found in the config file.
-== Load_elf_binary() ==
+=== Load_elf_binary() ===
 The function load_elf_binary() is an implementation of the load_binary() method of the linux_binfmt object, for ELF binaries. It is called by do_execve() when loading a new program for execution.
@@ Line 173: / Line 173: @@
 If any of the mnemonic names listed in the .memtypes NOTE section do not match any of the kernel’s node names, the node list is disabled for that segment (text or data). That is, the text/data memory region will not have node preferences, and will have pages allocated for that region from any available node.
-== load_elf_interp() ==
+=== load_elf_interp() ===
 Load_elf_interp() is called by load_elf_binary() when the latter function discovers a program header of type PT_INTERP. This header describes the interpreter program that is to be used to dynamically load the shared libraries that the program requires.
@@ Line 181: / Line 181: @@
 For MTA, load_elf_interp() locates and reads the NOTE section containing the memory types list from the interpreter binary, converts the list to node ID’s, and passes that information to do_mmap_nodelist() and do_brk_nodelist(). Just like load_elf_binary(), the node info is inserted into a structure of type struct node_list (described later).
-== The Program Interpreter (ld.so) ==
+=== The Program Interpreter (ld.so) ===
 Ld.so is actually the first piece of code to execute when a new program runs. Ld.so runs in user space, and it’s job is similar to load_elf_interp(). It loads (maps) the text, data, and bss segments of every shared object listed in the main program.
@@ Line 189: / Line 189: @@
 Because ld.so is part of glibc, a new version of glibc is required to load shared objects in the correct nodes.
-== memtypes_to_nodelist() ==
+=== memtypes_to_nodelist() ===
 The method that converts memory type mnemonics to a node list is memtypes_to_nodelist(), and it has the following interface: void memtypes_to_nodelist(struct node_list * nl, char * names, int size);
@@ Line 196: / Line 196: @@
 null-termination character in the buffer. The size argument is the total size of the buffer in bytes, including the null characters. The buffer must be a kernel buffer, it cannot be a user-space buffer. If any of the names in the buffer do not match any of the kernel’s node names, the node list is disabled by setting nl->depth to zero (see next).
-== The node_list Object ==
+=== The node_list Object ===
 The struct node_list object is defined as follows:
@@ Line 218: / Line 218: @@
 All of the kernel methods that take a node list as input (such as do_mmap_nodelist() and do_brk_nodelist()) call check_nodelist() to verify that the node list is valid. The section "Kernel API’s" below describes how each method behaves when given an invalid node list.
-== do_mmap_nodelist() and do_brk_nodelist()  ==
+=== do_mmap_nodelist() and do_brk_nodelist()  ===
 Load_elf_binary(), load_elf_interp(), and ld.so convert the .memtypes NOTE section from the ELF binary into a node list via memtypes_to_nodelist(), and pass the resultant struct node_list
@@ Line 253: / Line 253: @@
 described later.
-== setup_arg_pages() ==
+=== setup_arg_pages() ===
 Setup_arg_pages() is called by load_elf_binary() to create the memory region for the program’s stack, which includes the program stack and also the argument strings to the program and environment variables that the program inherited.  When setup_arg_pages() instantiates the new VMA for the stack region, it simply copies the struct node_list data_nodes from the memory descriptor to the new VMA.

@@ Line 410: / Line 410: @@
 In other words, for every line (region) printed by /proc/[pid]/maps, /proc/[pid]/nodemap also prints a line, showing the node ID of resident pages for that region.
-= Tracing MTA with Linux Trace Toolkit =
+== Tracing MTA with Linux Trace Toolkit ==
 Important MTA events are captured by the run-time creation of Linux Trace Toolkit (LTT) custom events for MTA. The following events are defined in include/linux/vmnode.h, and are called at the appropriate locations in the kernel where the corresponding events occur:

@@ Line 365: / Line 365: @@
 If the passed node_list pointer is non-NULL and enabled (depth is non-zero), but the list is invalid as indicated by check_nodelist(), the mapping fails, and both methods return -EINVAL.
-= User API’s =
+== User API’s ==
-== Mmap_memtypes() and brk_memtypes() ==
+=== Mmap_memtypes() and brk_memtypes() ===
 These new system calls are implemented to allow creating memory maps from user space with node information. They essentially provides user-level access to the kernel methods do_mmap_nodelist() and do_brk_nodelist(). The prototypes are the same as the current system calls, with two additional arguments:
@@ Line 395: / Line 395: @@
 *The usual conditions exist on the remaining arguments (for instance, for a file mapping the file descriptor must refer to a valid open file).
-== /proc Interface ==
+=== /proc Interface ===
 There are two new entries in the /proc file system.
-=== /proc/nodeinfo  ===
+==== /proc/nodeinfo  ====
 The first is /proc/nodeinfo, which lists the node configuration of the kernel, including the name, physical address range, and whether default page allocation is allowed, of each configured node.
-=== /proc/[pid]/nodemap ===
+==== /proc/[pid]/nodemap ====
 The second is an extension of the Memory Accounting tool. If the kernel config option CONFIG_MEMORY_ACCOUNTING is enabled along with CONFIG_MEMTYPE_ALLOC, a new proc entry, /proc/[pid]/nodemap will be available. The information is similar to the Memory Accounting Tool’

@@ Line 317: / Line 317: @@
 alloc_pages_nodelist() attempts allocation from the nodes in the following order before finally failing: 3 3 1.
-= Kernel API’s =
+== Kernel API’s ==
-== Allocating Whole Pages, alloc_pages_nodelist() ==
+=== Allocating Whole Pages, alloc_pages_nodelist() ===
-Device drivers or other kernel code that wish to allocate whole
+Device drivers or other kernel code that wish to allocate whole memory pages from a specific node can call alloc_pages_nodelist() directly. If the caller has a list of mnemonic strings, it must
-memory pages from a specific node can call alloc_pages_nodelist()
+first convert the strings to a node list with memtypes_to_nodelist() before calling alloc_pages_nodelist().
 directly. If the caller has a list of mnemonic strings, it must
 first convert the strings to a node list with memtypes_to_nodelist()
 before calling alloc_pages_nodelist().
 For sake of speed in allocating pages during page faults,
@@ Line 338: / Line 335: @@
 do_brk_nodelist() all check the validity of the list beforehand.
-== Slab Allocator, kmalloc_nodelist() ==
+=== Slab Allocator, kmalloc_nodelist() ===
-Device drivers or other kernel code that wish to allocate memory of
+Device drivers or other kernel code that wish to allocate memory of arbitrary size from a specific node can make use of a new interface to the slab allocator, kmalloc_nodelist(), which takes as an extra argument a pointer to a struct node_list object. It’s prototype is as follows:
 arbitrary size from a specific node can make use of a new interface
 to the slab allocator, kmalloc_nodelist(), which takes as an extra
 argument a pointer to a struct node_list object. It’s prototype is
 as follows:
 <pre>
@@ Line 359: / Line 352: @@
 </pre>
-The new cache can then be used when allocating objects by passing it
+The new cache can then be used when allocating objects by passing it to kmem_cache_alloc(). The new objects will be allocated from the nodes listed in the cache objects node list.
 to kmem_cache_alloc(). The new objects will be allocated from the
 nodes listed in the cache objects node list.
-Both of these new methods perform the following checks on the passed
+Both of these new methods perform the following checks on the passed node list:
 node list:
 *if the node list pointer is NULL, or the list is empty, the new slab object or cache will not have any node preference.
 *if the node list is invalid as indicated by check_nodelist(), both methods fail, returning NULL.
-== do_mmap_nodelist() and do_brk_nodelist() ==
+=== do_mmap_nodelist() and do_brk_nodelist() ===
-Kernel code that wishes to create new mappings for a process can
+Kernel code that wishes to create new mappings for a process can call do_mmap_nodelist() or do_brk_nodelist() directly. The current prototypes are identical to the original do_mmap() and do_brk(), with the addition of a node_list pointer as the last argument.
 call do_mmap_nodelist() or do_brk_nodelist() directly. The current
 prototypes are identical to the original do_mmap() and do_brk(),
 with the addition of a node_list pointer as the last argument.
-If the passed node_list pointer is non-NULL and enabled (depth is
+If the passed node_list pointer is non-NULL and enabled (depth is non-zero), but the list is invalid as indicated by check_nodelist(), the mapping fails, and both methods return -EINVAL.
 non-zero), but the list is invalid as indicated by check_nodelist(),
 the mapping fails, and both methods return -EINVAL.
 = User API’s =

@@ Line 284: / Line 284: @@
 == Allocating Pages With a Node List ==
-A wrapper function is provided to _ _alloc_pages() called
+A wrapper function is provided to _ _alloc_pages() called alloc_pages_node(), which takes as arguments the node ID of the memory node to allocate the pages from. It’s interface is:
 alloc_pages_node(), which takes as arguments the node ID of the
 memory node to allocate the pages from. It’s interface is:
 <pre>
@@ Line 300: / Line 298: @@
 </pre>
-The function is written so that plenty of opportunity is given for
+The function is written so that plenty of opportunity is given for allocation from the first choice node (nl->nid[0]) to succeed if the gfp_mask includes the _ _GFP_WAIT flag. Note that if _ _alloc_pages() returns NULL when the _ _GFP_WAIT flag is set, it means kswapd was allowed to run, and therefore pages may have become free in the first choice node, so we should try again.
 allocation from the first choice node (nl->nid[0]) to succeed if the
 gfp_mask includes the _ _GFP_WAIT flag. Note that if _ _alloc_pages()
 returns NULL when the _ _GFP_WAIT flag is set, it means kswapd was
 allowed to run, and therefore pages may have become free in the
 first choice node, so we should try again.
-Alloc_pages_nodelist() accomplishes this behavior with an outer and
+Alloc_pages_nodelist() accomplishes this behavior with an outer and inner loop (see the flow chart below for an illustration of the algorithm). The outer loop increments from zero to nl->depth, and the inner loop increments from zero to the current outer loop index. The inner loop attempts to allocate a page from nl->nid[j], where j is the inner loop index. The function returns on the first successfull page allocation. As described above, the underlying buddy system allocator, _ _alloc_pages(), will first attempt atomic allocation from the node, and if that fails, will yield to kswapd to free up pages, and then return NULL back to alloc_pages_nodelist().
 inner loop (see the flow chart below for an illustration of the
 algorithm). The outer loop increments from zero to nl->depth, and
 the inner loop increments from zero to the current outer loop
 index. The inner loop attempts to allocate a page from nl->nid[j],
 where j is the inner loop index. The function returns on the first
 successfull page allocation. As described above, the underlying
 buddy system allocator, _ _alloc_pages(), will first attempt atomic
 allocation from the node, and if that fails, will yield to kswapd to
 free up pages, and then return NULL back to alloc_pages_nodelist().
-As an example, suppose we have a node ID list containing {3,1}
+As an example, suppose we have a node ID list containing {3,1} (nl->depth is 2), and the _ _GFP_WAIT flag is set in gfp_mask. Assuming alloc_pages_nodelist() ultimately fails, it will
-(nl->depth is 2), and the _ _GFP_WAIT flag is set in
+attempt allocation from the nodes in the following order: 3 3 1 3 1. In other words:
 gfp_mask. Assuming alloc_pages_nodelist() ultimately fails, it will
 attempt allocation from the nodes in the following order:
 3 1 3 1. In other words:
 #kswapd runs after allocation from 1st choice node 3 fails.
@@ Line 330: / Line 311: @@
 #retry node 1 - fails again and giveup (return NULL).
-It is also possible to attempt allocation from the first choice node
+It is also possible to attempt allocation from the first choice node many times by repeating the node in the node list. For example, with a node ID list containing {3,3,1}, alloc_pages_nodelist() attempts allocation from the nodes in the following order before finally
 many times by repeating the node in the node list. For example, with
 a node ID list containing {3,3,1}, alloc_pages_nodelist() attempts
 allocation from the nodes in the following order before finally
 failing: 3 3 3 3 3 1 3 3 1.
-Note that if the _ _GFP_WAIT flag is not set, the inner loop is
+Note that if the _ _GFP_WAIT flag is not set, the inner loop is collapsed, and each node in the list is tried in sequence with no retries. So given the node list {3,3,1} from the example above,
-collapsed, and each node in the list is tried in sequence with no
+alloc_pages_nodelist() attempts allocation from the nodes in the following order before finally failing: 3 3 1.
 retries. So given the node list {3,3,1} from the example above,
 alloc_pages_nodelist() attempts allocation from the nodes in the
 following order before finally failing: 3 3 1.
 = Kernel API’s =

@@ Line 279: / Line 279: @@
 == Default Page Allocator ==
-The default page allocator is _alloc_pages(). It attempts to
+The default page allocator is _alloc_pages(). It attempts to allocate from any available node in a round-robin manner.  This method has been slightly modified for MTA. Each configured node in
-allocate from any available node in a round-robin manner.  This
+MTA includes a flag specifying whether _alloc_pages() is allowed to allocate pages from that node. This flag can thus be used to reserve an entire node only for MTA allocation. An example use might be a node containing a very small number of physical pages. By reserving the node only for MTA allocation, it guarantees that it will only be used to allocate pages for process memory region’s that specify node lists, or for any caller of alloc_pages_nodelist() (described next).
 method has been slightly modified for MTA. Each configured node in
 MTA includes a flag specifying whether _alloc_pages() is allowed to
 allocate pages from that node. This flag can thus be used to reserve
 an entire node only for MTA allocation. An example use might be a
 node containing a very small number of physical pages. By reserving
 the node only for MTA allocation, it guarantees that it will only be
 used to allocate pages for process memory region’s that specify
 node lists, or for any caller of alloc_pages_nodelist() (described
 next).
 == Allocating Pages With a Node List ==