Physical Memory Management [0/1]

Hello everyone,

In the next message a patch which allows allocation of large continuous blocks of physical memory will be sent. This functionality makes it similar to bigphysarea, however PMM has many more features:

1. Each allocated block of memory has a reference counter so different kernel modules may share the same buffer with a well known get/put semantics.

2. It aggregates physical memory allocating and management API in one place. This is good because there is a single place to debug and test for all devices. Moreover, because each device does not need to reserve it's own area of physical memory a total size of reserved memory is smaller. Say, we have 3 accelerators. Each of them can operate on 1MiB blocks, so each of them would have to reserve 1MiB for itself (this means total of 3MiB of reserved memory). However, if at most two of those devices can be used at once, we could reserve 2MiB saving 1MiB.

3. PMM has it's own allocator which runs in O(log n) bound time where n is total number of areas and free spaces between them -- the upper time limit may be important when working on data sent in real time (for instance an output of a camera). Currently a best-fit algorithm is used but you can easily replace it if it does not meet your needs.

4. Via a misc char device, the module allows allocation of continuous blocks from user space. Such solution has several advantages. In particular, other option would be to add a allocation calls for each individual devices (think hardware accelerators) -- this would double the same code in several drivers plus it would lead to inconsistent API for doing the very same think. Moreover, when creating pipelines (ie. encoded image --[decoder]--> decoded image --[scaler]--> scaled image) devices would have to develop a method of sharing buffers. With PMM user space program allocates a block and passes it as an output buffer for the first device and input buffer for the other.

5. PMM is integrated with System V IPC, so that user space programs may "convert" allocated block into a segment of System V shared memory. This makes it possible to pass PMM buffers to PMM-unaware but SysV-aware applications. Notable example are X11. This makes it possible to deploy a zero-copy scheme when communicating with X11. For instance, image scaled in previous example could be passed directly to X server without the need to copy it to a newly created System V shared memory.

6. PMM has a notion of memory types. In attached patch only a general memory type is defined but you can easily add more types for a given platform. To understand what in PMM terms is memory type we can use an example: a general memory may be a main RAM memory which we have a lot but it is quite slow and another type may be a portion of L2 cache configured to act as fast memory. Because PMM may be aware of those, again, allocation of different kinds of memory has a common, consistent API.

As the patch is quite large, it will be attached to the next message. It is also available at <URL:http://home.elka.pw.edu.pl/~mnazarew/pmm.diff>.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  Michal‚ "mina86" Nazarewicz     (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

Physical Memory Management (or PMM) added

PMM allows allocation of continiuous blocks of physical memory. Via a device and ioctl(2) calls it allows allocation to be made from user space. Moreover, it can be integrated with System V IPC allowing PMM-unaware but shmem-aware programs (notably X11) use shared continiuous blocks of physical memory.

new file mode 100644
index 0000000..bf6febe
@@ -0,0 +1,146 @@
+#ifndef __KERNEL_PMM_H
+#define __KERNEL_PMM_H
+
+/*
+ * Physical Memory Managment module
+ * Copyright (c) 2009 by Samsung Electronics.  All rights reserved.
+ * Written by Michal Nazarewicz ([email protected])
+ */
+
+
+#include <linux/ioctl.h>
+
+
+
+#if defined CONFIG_PMM_PLATFORM_HAS_OWN_INIT
+   /* Definition of platform dependend memory types. */
+#  include <asm/pmm-plat.h>
+#else
+/**
+ * Number of types of memory.  Must be positive number no greater then
+ * 16 (in fact 32 but let keep it under 16).
+ */
+#  define PMM_MEMORY_TYPES  1
+
+/** A general purpose memory. */
+#define PMM_MEM_GENERAL     1
+
+
+#  ifdef __KERNEL__
+
+/** Mask of types that user space tools can allocate. */
+#    define PMM_USER_MEMORY_TYPES_MASK 1
+
+#  endif
+
+#endif
+
+
+
+/** An information about area exportable to user space. */
+struct pmm_area_info {
+	unsigned magic;      /**< Magic number (must be PMM_MAGIC) */
+	size_t   size;       /**< Size of the area */
+	unsigned type;       /**< Memory's type */
+	unsigned flags;      /**< Flags (unused as of yet) */
+	size_t   alignment;   /**< Area's alignment as a power of two */
+};
+
+/** Value of pmm_area_info::magic field. */
+#define PMM_MAGIC (('p' << 24) | ('M' << 16) | ('m' << 8) | 0x42)
+
+
+/**
+ * Allocates area.  Accepts struct pmm_area_info as in/out
+ * argument.  Meaning of each field is as follows:
+ * - size     size in bytes of desired area.
+ * - type     mask of types to allocate from
+ * - flags    additional flags (no flags defined yet)
+ * - alignment area's alignment as a power of two
+ * Returns area's key or -1 on error.
+ */
+#define IOCTL_PMM_ALLOC    _IOWR('p', 0, struct pmm_area_info)
+
+
+
+struct pmm_shm_info {
+	unsigned magic;      /**< Magic number (must be PMM_MAGIC) */
+	key_t    key;
+	int      shmflg;
+};
+
+/* TODO document */
+#define IOCTL_PMM_SHMGET   _IOR('p', 0, struct pmm_shm_info)
+
+
+
+
+#if __KERNEL__
+
+
+/**
+ * Allocates continuous block of memory.  Allocated area must be
+ * released (@see pmm_release()) when code no longer uses it.
+ * Arguments to the function are passed in a pmm_area_info
+ * structure (which see).  Meaning of each is described below:
+ *
+ * \a info->u.size specifies how large the area shall be.  It must
+ * be page aligned.
+ *
+ * \a info->u.type is a bitwise OR of all memory types that should be
+ * tried.  The module may define several types of memory and user
+ * space programs may desire to allocate areas of different types.
+ * This attribute specifies what types user space tool is interested
+ * in.  Area will be allocated in first type that had enough space.
+ *
+ * \a info->u.flags is a bitwise OR of additional flags.  None are
+ * defined as of yet.
+ *
+ * \a info->u.alignment specifies size alignment of a physical
+ * address of the area.  It must be power of two or zero.  If given,
+ * physical address will be a multiple of that value.  In fact, the
+ * area may have a bigger alignment -- the final alignment will be saved
+ * in info structure.
+ *
+ * If the area is allocated sucesfully \a info is filled with
+ * information about the area.
+ *
+ * @param  info    input/output argument
+ * @return area's physical address or zero on error
+ */
+__must_check
+size_t pmm_alloc(struct pmm_area_info *info);
+
+
+/**
+ * Increases PMM's area reference counter.
+ * @param  addr block's physical address.
+ * @return zero on success, negative on error
+ */
+int    pmm_get(size_t paddr);
+
+/**
+ * Decreases PMM's area reference counter and possibly frees it if it
+ * reaches zero.
+ *
+ * @param  addr block's physical address.
+ * @return zero on success, negative on error
+ */
+int    pmm_put(size_t paddr);
+
+
+
+#if defined CONFIG_PMM_PLATFORM_HAS_OWN_INIT
+
+typedef int (*pmm_add_region_func)(size_t paddr, size_t size,
+                                   unsigned type, unsigned flags);
+
+/** Defined by platform, used by pmm_module_init(). */
+void pmm_module_platform_init(pmm_add_region_func add_region);
+
+#endif /* CONFIG_PMM_PLATFORM_HAS_OWN_INIT */
+
+
+#endif /* __KERNEL__ */
+
+#endif /* __KERNEL_PMM_H */

index 05d51d2..6a7c68f 100644
@@ -805,6 +805,10 @@ out:
  */
 long do_shmat(int shmid, char __user *shmaddr, int shmflg, ulong *raddr)
 {
+#if defined CONFIG_PMM_SHM
+	extern const struct file_operations pmm_fops;
+#endif
+
 	struct shmid_kernel *shp;
 	unsigned long addr;
 	unsigned long size;

@@ -876,7 +880,14 @@ long do_shmat(int shmid, char __user *shmaddr, int shmflg, ulong *raddr)
 	path.dentry = dget(shp->shm_file->f_path.dentry);
 	path.mnt    = shp->shm_file->f_path.mnt;
 	shp->shm_nattch++;
-	size = i_size_read(path.dentry->d_inode);
+
+#if defined CONFIG_PMM_SHM
+	if (shp->shm_file->f_op == &pmm_fops)
+		size = *(size_t *)shp->shm_file->private_data;
+	else
+#endif
+		size = i_size_read(path.dentry->d_inode);
+
 	shm_unlock(shp);
 
 	err = -ENOMEM;

@@ -963,6 +974,10 @@ SYSCALL_DEFINE3(shmat, int, shmid, char __user *, shmaddr, int, shmflg)
  */
 SYSCALL_DEFINE1(shmdt, char __user *, shmaddr)
 {
+#if defined CONFIG_PMM_SHM
+	extern const struct file_operations pmm_fops;
+#endif
+
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma, *next;
 	unsigned long addr = (unsigned long)shmaddr;

@@ -1009,7 +1024,13 @@ SYSCALL_DEFINE1(shmdt, char __user *, shmaddr)
 			(vma->vm_start - addr)/PAGE_SIZE == vma->vm_pgoff) {
 
 
-			size = vma->vm_file->f_path.dentry->d_inode->i_size;
+#if defined CONFIG_PMM_SHM
+			if (shm_file_data(vma->vm_file)->file->f_op ==
+			    &pmm_fops) {
+				size = *(size_t *)vma->vm_file->private_data;
+			} else
+#endif
+				size = vma->vm_file->f_path.dentry->d_inode->i_size;
 			do_munmap(mm, vma->vm_start, vma->vm_end - vma->vm_start);
 			/*
 			 * We discovered the size of the shm segment, so

index 72255be..0c5d5c4 100644
@@ -33,3 +33,5 @@ obj-$(CONFIG_MIGRATION) += migrate.o
 obj-$(CONFIG_SMP) += allocpercpu.o
 obj-$(CONFIG_QUICKLIST) += quicklist.o
 obj-$(CONFIG_CGROUP_MEM_RES_CTLR) += memcontrol.o page_cgroup.o
+obj-$(CONFIG_PMM) += pmm.o
+obj-$(CONFIG_PMM_USE_OWN_INIT) += pmm-init.o

(cc linux-mm)

(please keep the emails to under 80 columns)

OK, let's pretend we didn't see an implementation.

What are you trying to do here? What problem(s) are being solved? What are the requirements and the use cases?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Yes, sorry about that. Apparently "Automatically wrap outgoing messages" doesn't mean what I thought it does.

:]

I've never said it's perfect. I'll welcome any constructive comments.

Overall situation: UMA embedded system and many hardware accelerators (DMA capable, no scatter-gather). Three use cases:

1. We have a hardware JPEG decoder, we want to decode an image.

2. As above plus we have an image scaler, we want to scale decoded image.

3. As above plus we want to pass scaled image to X server.

Neither decoder nor scaler may operate on malloc(3)ed areas as they aren't continuous in physical memory. A copying of a scattered buffer would have to be used. This is a performance cost. It also doubles memory usage.

PMM solves this as it lets user space allocate a continuous buffers which the devices may use directly.

It could be solved by letting each driver allocate its own buffers during boot time and then let user space mmap(2) them. However, with 10 hardware accelerators each needing 1MiB buffer we need to reserve 10MiB of memory. If we know that at most 5 devices will be used at the same time we could've reserve 5MiB instead of 10MiB.

PMM solves this problem since the buffers are allocated when they are needed.

This could be solved by letting each driver allocate buffers when requested (using bigphysarea for instance). It has some minor issues like implementing mmap file operation in all drivers and inconsistent user space API but the most significant is it's not clear how to implement 2nd use case. If drivers expect to work on their own buffers, decoder's output must be copied into scaler's input buffer.

With PMM, drivers simply expect a continuous buffers and do not care where they came from or if other drivers use them as well.

Now, as of 3rd use case. X may work with System V shared memory, however, since shared memory segments (created via shmget(2)) are not continuous, we cannot pass it to a scaler as an output buffer.

PMM solves it, since it allows converting an area allocated via PMM into a System V shared memory segment.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ha - only when you actually manage to allocate things. Physically contiguous allocations are exceedingly hard once the machine has been running for a while.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

PMM reserves memory during boot time using alloc_bootmem_low_pages(). After this is done, it can allocate buffers from reserved pool.

The idea here is that there are n hardware accelerators, each can operate on 1MiB blocks (to simplify assume that's the case). However, we know that at most m < n devices will be used at the same time so instead of reserving n MiBs of memory we reserve only m MiBs.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

And who says your pre-allocated pool won't fragment with repeated PMM use?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Yes, this is a good question. What's more, there's no good answer. ;)

There is no guarantee and it depends on use cases. The biggest problem is a lot of small buffers allocated by different applications which get freed at different times. However, if in most cases one or two applications use PMM, we can assume that buffers are allocated and freed in groups. If that's the case, fragmentation is less likely to occur.

I'm not claiming that PMM is panacea for all the problems present on systems with no scatter-gather capability -- it is an attempt to gather different functionality and existing solutions in one place which is easier to manage and improve if needed.

Problem with allocation of continuous blocks hos no universal solution -- you can increased reserved area but then overall performance of the system will decrease. PMM is trying to find a compromise between the two.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

We do have capability in page reclaim to deliberately free up physically contiguous pages (known as "lumpy reclaim").

It would be interesting were someone to have a go at making that available to userspace: ask the kernel to give you 1MB of physically contiguous memory. There are reasons why this can fail, but migrating pages can be used to improve the success rate, and userspace can be careful to not go nuts using mlock(), etc.

The returned memory would of course need to be protected from other reclaim/migration/etc activity.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I thought we already exposed this, its called hugetlbfs ;-)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Doesn't this require swap?

Correct me if I'm wrong, but if I understand correctly, currently only one size of huge page may be defined, even if underlaying architecture supports many different sizes.

So now, there are two cases: (i) either define huge page size to the largest blocks that may ever be requested and then waste a lot of memory when small pages are requested or (ii) define smaller huge page size but then special handling of large regions need to be implemented.

The first solution is not acceptable, as a lot of memory may be wasted. If for example, you have a 4 mega pixel camera you'd have to configure 4 MiB-large huge pages but in most cases, you won't be needing that much. Often you will work with say 320x200x2 images (125KiB) and more then 3MiBs will be wasted!

In the later, with (say) 128 KiB huge pages no (or little) space will be wasted when working with 320x200x2 images but then when someone would really need 4 MiB to take a photo the very same problem we started with will occur -- we will have to find 32 contiguous pages.

So to sum up, if I understand everything correctly, hugetlb would be a great solution when working with buffers of similar sizes. However, it's not so good when size of requested buffer may vary greatly.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

That's not correct, support for multiple huge page sizes was recently added. The interface is a bit clumpsy admittedly, but it's there.

However for non fragmentation purposes you probably don't want too many different sizes anyways, the more sizes, the worse the fragmentation. Ideal is only a single size.

If you don't do that then long term fragmentation will kill you anyways. it's easy to show that pre allocation with lots of different sizes is about equivalent what the main page allocator does anyways.

As Peter et.al. explained earlier varying buffer sizes don't work anyways.

-Andi

[email protected] -- Speaking for myself only.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I'll have to look into that further then. Having said that, I cannot create a huge page SysV shared memory segment with pages of specified size, can I?

Unfortunately, sizes may very from several KiBs to a few MiBs. On the other hand, only a handful of apps will use PMM in our system and at most two or three will be run at the same time so hopefully fragmentation won't be so bad. But yes, I admit it is a concern.

However, having an allocator in PMM used by a handful of apps, an architect may provide a use cases that need to be supported and then PMM may be reimplemented to guarantee that those cases are handled.

Either I missed something or Peter and Adrew only pointed the problem we all seem to agree exists: a problem of fragmentation.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Well, hugetlbfs is a fs, so you can simply create a file on there and map that shared -- much saner interface than sysvshm if you ask me.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

It's not a question of being sane or not, it's a question of whether X server supports it and it doesn't. X can read data from Sys V shm to avoid needles copying (or sending via unix socket or whatever) pixmaps (or whatever) and so PMM lets it read from continuous blocks without knowing or carying about it.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

sysv shared memory supports huge pages, but there is currently no interface to specify the intended page size, you always get the default.

Then your approach will likely not be reliable.

Such tight restrictions might work for you, but for mainline Linux the quality standards are higher.

Multiple buffer sizes lead to fragmentation.

-Andi

[email protected] -- Speaking for myself only.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I understand PMM in current form may be unacceptable, however, hear me out and please do correct me if I'm wrong at any point as I would love to use an existing solution if any fulfilling my needs is present:

When different sizes of buffers are needed fragmentation is even bigger problem in hugetlb (as pages must be aligned) then with PMM.

If a buffer that does not match page size is needed then with hugetlb either bigger page needs to be allocated (and memory wasted) or few smaller need to be merged (and the same problem as in PMM exists -- finding contiguous pages).

Reclaiming is not really an option since situation where there is no sane bound time for allocation is not acceptable -- you don't want to wait 10 seconds for an application to start on your cell phone. ;)

Also, I need an ability to convert any buffer to a Sys V shm, as to be able to pass it to X server. Currently no such API exist, does it?

With PMM and it's notion of memory types, different allocators and/or memory pools, etc. Allocators could be even dynamically loaded as modules if one desires that. My point is, that PMM is to be considered a framework for situations similar to the one I described thorough all of my mails, rather then a universal solution.

Best regards,                                            _     _
 .o. | Liege of Serenly Enlightened Majesty of         o' \,=./ `o
 ..o | Computer Science,  MichaA? "mina86" Nazarewicz      (o o)
 ooo +-<[email protected]>-<[email protected]>-ooO--(_)--Ooo--

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

You could just define a hugepage size for that and use hugetlbfs with a few changes to map in pages with multiple PTEs. It supports boot time reservation and is a well established interface.

On x86 that would give 2MB units, on other architectures whatever you prefer.

-Andi

[email protected] -- Speaking for myself only.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>