From patchwork Tue Jun 11 02:11:20 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Stultz X-Patchwork-Id: 17760 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-ve0-f198.google.com (mail-ve0-f198.google.com [209.85.128.198]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id C7D902397B for ; Tue, 11 Jun 2013 02:11:40 +0000 (UTC) Received: by mail-ve0-f198.google.com with SMTP id jz10sf7893849veb.5 for ; Mon, 10 Jun 2013 19:11:40 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:x-beenthere:x-forwarded-to:x-forwarded-for :delivered-to:from:to:cc:subject:date:message-id:x-mailer :in-reply-to:references:x-gm-message-state:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :x-google-group-id:list-post:list-help:list-archive:list-unsubscribe; bh=oP9yCqOKd3ap2/qbfMKu4VldUgp3kWRsSKGp309phGU=; b=BgHu2iLWtWS9rvMapee46kqr7bpWTE9N1q+KDR77z4k7U2gEsRmjtQOd1jHrwAL/HH l1q2xleeSpbv5H1xuwn+OQC5jn1GgLqSZn2JqEiKTB8n6IPNiIjdMJT3MFiwe3PxQWRc 8RF1t3kG0FRc4FMGVzc9+t0xspQOTZM5u/601M/2ScFaQ+xVTe4bzx/GFimrHLUMLsKm P4+hoxzXeWNnerlD8NVc/fVcudlL/LfcKVTO/10awpwkPRDdFiEw58VKFdpxE/mKlSZe szeRXJA8/YeoA2TTbUgqc/giS9URelq9g7lCxWWsae/LO7n26Tw6C6njIbeO0gd0Rs/l isMg== X-Received: by 10.236.133.19 with SMTP id p19mr7528685yhi.54.1370916700402; Mon, 10 Jun 2013 19:11:40 -0700 (PDT) MIME-Version: 1.0 X-BeenThere: patchwork-forward@linaro.org Received: by 10.49.117.104 with SMTP id kd8ls3076809qeb.93.gmail; Mon, 10 Jun 2013 19:11:40 -0700 (PDT) X-Received: by 10.52.88.107 with SMTP id bf11mr6027666vdb.115.1370916700163; Mon, 10 Jun 2013 19:11:40 -0700 (PDT) Received: from mail-ve0-x22d.google.com (mail-ve0-x22d.google.com [2607:f8b0:400c:c01::22d]) by mx.google.com with ESMTPS id i3si6189814vdw.152.2013.06.10.19.11.40 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 10 Jun 2013 19:11:40 -0700 (PDT) Received-SPF: neutral (google.com: 2607:f8b0:400c:c01::22d is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=2607:f8b0:400c:c01::22d; Received: by mail-ve0-f173.google.com with SMTP id jw11so5339738veb.4 for ; Mon, 10 Jun 2013 19:11:40 -0700 (PDT) X-Received: by 10.52.157.138 with SMTP id wm10mr6155394vdb.57.1370916700015; Mon, 10 Jun 2013 19:11:40 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patches@linaro.org Received: by 10.221.10.206 with SMTP id pb14csp90900vcb; Mon, 10 Jun 2013 19:11:39 -0700 (PDT) X-Received: by 10.68.1.226 with SMTP id 2mr12552386pbp.150.1370916698610; Mon, 10 Jun 2013 19:11:38 -0700 (PDT) Received: from mail-pb0-x22e.google.com (mail-pb0-x22e.google.com [2607:f8b0:400e:c01::22e]) by mx.google.com with ESMTPS id tr9si5889972pbc.313.2013.06.10.19.11.38 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 10 Jun 2013 19:11:38 -0700 (PDT) Received-SPF: neutral (google.com: 2607:f8b0:400e:c01::22e is neither permitted nor denied by best guess record for domain of john.stultz@linaro.org) client-ip=2607:f8b0:400e:c01::22e; Received: by mail-pb0-f46.google.com with SMTP id rq2so2863233pbb.5 for ; Mon, 10 Jun 2013 19:11:38 -0700 (PDT) X-Received: by 10.68.110.131 with SMTP id ia3mr12278529pbb.181.1370916697984; Mon, 10 Jun 2013 19:11:37 -0700 (PDT) Received: from localhost.localdomain (c-67-170-153-23.hsd1.or.comcast.net. [67.170.153.23]) by mx.google.com with ESMTPSA id nt2sm12427175pbc.17.2013.06.10.19.11.36 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Mon, 10 Jun 2013 19:11:37 -0700 (PDT) From: John Stultz To: minchan.kim@lge.com Cc: Minchan Kim , John Stultz Subject: [PATCH 01/13] vrange: Add basic data structure and functions Date: Mon, 10 Jun 2013 19:11:20 -0700 Message-Id: <1370916692-9576-2-git-send-email-john.stultz@linaro.org> X-Mailer: git-send-email 1.8.1.2 In-Reply-To: <1370916692-9576-1-git-send-email-john.stultz@linaro.org> References: <1370916692-9576-1-git-send-email-john.stultz@linaro.org> X-Gm-Message-State: ALoCoQkCdyIQuwpOoJeBrfeSwRCTK9irqIGwfquaBq8tLxsT4mxcOs0S32M7bnTCmQ/H8LKuy3Xr X-Original-Sender: john.stultz@linaro.org X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 2607:f8b0:400c:c01::22d is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Precedence: list Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org List-ID: X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , From: Minchan Kim This patch adds vrange data structure(interval tree) and related functions. The vrange uses generic interval tree as main data structure because it handles address range so generic interval tree fits well for the purpose. The add_vrange/remove_vrange are core functions for system call will be introduced next patch. 1. add_vrange inserts new address range into interval tree. If new address range crosses over existing volatile range, existing volatile range will be expanded to cover new range. Then, if existing volatile range has purged state, new range will have a purged state. It's not good and we need more fine-grained purged state handling in a vrange(TODO) If new address range is inside existing range, we ignore it 2. remove_vrange removes address range Then, return a purged state of the address ranges. This patch copied some part from John Stultz's work but different semantic. Signed-off-by: John Stultz Signed-off-by: Minchan Kim [jstultz: Heavy rework and cleanups to make this infrastructure more easily reused for both file and anonymous pages] Signed-off-by: John Stultz --- include/linux/vrange.h | 44 +++++++++++ include/linux/vrange_types.h | 19 +++++ init/main.c | 2 + lib/Makefile | 2 +- mm/Makefile | 2 +- mm/vrange.c | 181 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 248 insertions(+), 2 deletions(-) create mode 100644 include/linux/vrange.h create mode 100644 include/linux/vrange_types.h create mode 100644 mm/vrange.c diff --git a/include/linux/vrange.h b/include/linux/vrange.h new file mode 100644 index 0000000..2064cb0 --- /dev/null +++ b/include/linux/vrange.h @@ -0,0 +1,44 @@ +#ifndef _LINUX_VRANGE_H +#define _LINUX_VRANGE_H + +#include +#include + +#define vrange_entry(ptr) \ + container_of(ptr, struct vrange, node.rb) + +#ifdef CONFIG_MMU + +static inline void vrange_root_init(struct vrange_root *vroot, int type) +{ + vroot->type = type; + vroot->v_rb = RB_ROOT; + mutex_init(&vroot->v_lock); +} + +static inline void vrange_lock(struct vrange_root *vroot) +{ + mutex_lock(&vroot->v_lock); +} + +static inline void vrange_unlock(struct vrange_root *vroot) +{ + mutex_unlock(&vroot->v_lock); +} + +static inline int vrange_type(struct vrange *vrange) +{ + return vrange->owner->type; +} + +void vrange_init(void); +extern void vrange_root_cleanup(struct vrange_root *vroot); + +#else + +static inline void vrange_init(void) {}; +static inline void vrange_root_init(struct vrange_root *vroot, int type) {}; +static inline void vrange_root_cleanup(struct vrange_root *vroot) {}; + +#endif +#endif /* _LINIUX_VRANGE_H */ diff --git a/include/linux/vrange_types.h b/include/linux/vrange_types.h new file mode 100644 index 0000000..7f44c01 --- /dev/null +++ b/include/linux/vrange_types.h @@ -0,0 +1,19 @@ +#ifndef _LINUX_VRANGE_TYPES_H +#define _LINUX_VRANGE_TYPES_H + +#include +#include + +struct vrange_root { + struct rb_root v_rb; /* vrange rb tree */ + struct mutex v_lock; /* Protect v_rb */ + enum {VRANGE_MM, VRANGE_FILE} type; /* range root type */ +}; + +struct vrange { + struct interval_tree_node node; + struct vrange_root *owner; + int purged; +}; +#endif + diff --git a/init/main.c b/init/main.c index 9484f4b..9cf08ba 100644 --- a/init/main.c +++ b/init/main.c @@ -74,6 +74,7 @@ #include #include #include +#include #include #include @@ -601,6 +602,7 @@ asmlinkage void __init start_kernel(void) calibrate_delay(); pidmap_init(); anon_vma_init(); + vrange_init(); #ifdef CONFIG_X86 if (efi_enabled(EFI_RUNTIME_SERVICES)) efi_enter_virtual_mode(); diff --git a/lib/Makefile b/lib/Makefile index c55a037..ccd15ff 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ - earlycpio.o + earlycpio.o interval_tree.o obj-$(CONFIG_ARCH_HAS_DEBUG_STRICT_USER_COPY_CHECKS) += usercopy.o lib-$(CONFIG_MMU) += ioremap.o diff --git a/mm/Makefile b/mm/Makefile index 72c5acb..b67fcf5 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -5,7 +5,7 @@ mmu-y := nommu.o mmu-$(CONFIG_MMU) := fremap.o highmem.o madvise.o memory.o mincore.o \ mlock.o mmap.o mprotect.o mremap.o msync.o rmap.o \ - vmalloc.o pagewalk.o pgtable-generic.o + vmalloc.o pagewalk.o pgtable-generic.o vrange.o ifdef CONFIG_CROSS_MEMORY_ATTACH mmu-$(CONFIG_MMU) += process_vm_access.o diff --git a/mm/vrange.c b/mm/vrange.c new file mode 100644 index 0000000..e3042e0 --- /dev/null +++ b/mm/vrange.c @@ -0,0 +1,181 @@ +/* + * mm/vrange.c + */ + +#include +#include + +static struct kmem_cache *vrange_cachep; + +void __init vrange_init(void) +{ + vrange_cachep = KMEM_CACHE(vrange, SLAB_PANIC); +} + +static struct vrange *__vrange_alloc(gfp_t flags) +{ + struct vrange *vrange = kmem_cache_alloc(vrange_cachep, flags); + if (!vrange) + return vrange; + vrange->owner = NULL; + return vrange; +} + +static void __vrange_free(struct vrange *range) +{ + WARN_ON(range->owner); + kmem_cache_free(vrange_cachep, range); +} + +static void __vrange_add(struct vrange *range, struct vrange_root *vroot) +{ + range->owner = vroot; + interval_tree_insert(&range->node, &vroot->v_rb); +} + +static void __vrange_remove(struct vrange *range) +{ + interval_tree_remove(&range->node, &range->owner->v_rb); + range->owner = NULL; +} + +static inline void __vrange_set(struct vrange *range, + unsigned long start_idx, unsigned long end_idx, + bool purged) +{ + range->node.start = start_idx; + range->node.last = end_idx; + range->purged = purged; +} + +static inline void __vrange_resize(struct vrange *range, + unsigned long start_idx, unsigned long end_idx) +{ + struct vrange_root *vroot = range->owner; + bool purged = range->purged; + + __vrange_remove(range); + __vrange_set(range, start_idx, end_idx, purged); + __vrange_add(range, vroot); +} + +static int vrange_add(struct vrange_root *vroot, + unsigned long start_idx, unsigned long end_idx) +{ + struct vrange *new_range, *range; + struct interval_tree_node *node, *next; + int purged = 0; + + new_range = __vrange_alloc(GFP_KERNEL); + if (!new_range) + return -ENOMEM; + + vrange_lock(vroot); + + node = interval_tree_iter_first(&vroot->v_rb, start_idx, end_idx); + while (node) { + next = interval_tree_iter_next(node, start_idx, end_idx); + range = container_of(node, struct vrange, node); + /* old range covers new range fully */ + if (node->start <= start_idx && node->last >= end_idx) { + __vrange_free(new_range); + goto out; + } + + start_idx = min_t(unsigned long, start_idx, node->start); + end_idx = max_t(unsigned long, end_idx, node->last); + purged |= range->purged; + + __vrange_remove(range); + __vrange_free(range); + + node = next; + } + + __vrange_set(new_range, start_idx, end_idx, purged); + __vrange_add(new_range, vroot); +out: + vrange_unlock(vroot); + return 0; +} + +static int vrange_remove(struct vrange_root *vroot, + unsigned long start_idx, unsigned long end_idx, + int *purged) +{ + struct vrange *new_range, *range; + struct interval_tree_node *node, *next; + bool used_new = false; + + if (!purged) + return -EINVAL; + + *purged = 0; + + new_range = __vrange_alloc(GFP_KERNEL); + if (!new_range) + return -ENOMEM; + + vrange_lock(vroot); + + node = interval_tree_iter_first(&vroot->v_rb, start_idx, end_idx); + while (node) { + next = interval_tree_iter_next(node, start_idx, end_idx); + range = container_of(node, struct vrange, node); + + *purged |= range->purged; + + if (start_idx <= node->start && end_idx >= node->last) { + /* argumented range covers the range fully */ + __vrange_remove(range); + __vrange_free(range); + } else if (node->start >= start_idx) { + /* + * Argumented range covers over the left of the + * range + */ + __vrange_resize(range, end_idx + 1, node->last); + } else if (node->last <= end_idx) { + /* + * Argumented range covers over the right of the + * range + */ + __vrange_resize(range, node->start, start_idx - 1); + } else { + /* + * Argumented range is middle of the range + */ + used_new = true; + __vrange_resize(range, node->start, start_idx - 1); + __vrange_set(new_range, end_idx + 1, node->last, + range->purged); + __vrange_add(new_range, vroot); + break; + } + + node = next; + } + vrange_unlock(vroot); + + if (!used_new) + __vrange_free(new_range); + + return 0; +} + +void vrange_root_cleanup(struct vrange_root *vroot) +{ + struct vrange *range; + struct rb_node *next; + + vrange_lock(vroot); + next = rb_first(&vroot->v_rb); + while (next) { + range = vrange_entry(next); + next = rb_next(next); + __vrange_remove(range); + __vrange_free(range); + } + vrange_unlock(vroot); +} +