From: Timo Kokkonen Date: Sat, 15 Oct 2011 18:02:26 +0000 (+0300) Subject: Replace bintree with rbtree implementation X-Git-Url: http://git.itanic.dy.fi/?p=scan-pagemap;a=commitdiff_plain;h=9778934872cd83a6f5c06bc981381212b3e120b3 Replace bintree with rbtree implementation The biggest flaw with the bintree is that they can easily become unbalanced. For example, if X server maps the video card memory into its address space as 1:1 mapping, running scan-pagemap can be really slow. This is because reading the 1:1 mapping will generate horribly skewed binary tree that resembles more closely a single direction linked list. Replacing the simple binary tree implementation with the red black tree can make full scan over five times faster. Signed-off-by: Timo Kokkonen --- diff --git a/Makefile b/Makefile index a097dc0..1209700 100644 --- a/Makefile +++ b/Makefile @@ -4,7 +4,7 @@ CC=gcc SPARSE=sparse CHECKPATCH=/usr/src/linux/scripts/checkpatch.pl -SCAN_PAGEMAP_OBJS=main.o parse.o bintree.o analyze.o pidlib.o +SCAN_PAGEMAP_OBJS=main.o parse.o treeops.o analyze.o pidlib.o rbtree.o SCAN_PAGEMAP_DEBUG_OBJS= $(patsubst %.o,%-debug.o,$(SCAN_PAGEMAP_OBJS)) ALL_OBJS = $(SCAN_PAGEMAP_OBJS) $(SCAN_PAGEMAP_DEBUG_OBJS) ALL_DEBS = $(patsubst %.o,.%.o.d,$(ALL_OBJS)) diff --git a/analyze.c b/analyze.c index 57d0869..a032eff 100644 --- a/analyze.c +++ b/analyze.c @@ -20,7 +20,6 @@ #include "analyze.h" #include "utils.h" -#include "bintree.h" struct kpageflag_str kpageflag_str[] = { { .flag = LOCKED, .str = "locked", }, @@ -67,8 +66,6 @@ struct kpageflag_str kpageflag_str[] = { #define PAGE_TO_NICE_UNIT(a) NICE_UNIT((long long)a * PAGE_SIZE) struct analyze_frames { - struct bintree_ops ops; - int pid; struct list_head *pidlist; @@ -87,97 +84,106 @@ struct analyze_frames { #define bintree_ops_to_af(bintree_ops) \ container_of((bintree_ops), struct analyze_frames, ops) -static void count_pages(struct bintree *b, struct bintree_ops *ops) +static int count_pages(struct rb_root *root, struct analyze_frames *af) { - struct pageframe *pf = tree_to_pageframe(b); - struct analyze_frames *af = bintree_ops_to_af(ops); + struct pageframe *pf; struct maps_list *ml; - int i; + int i, pages = 0; - if (af->pid) { - /* Find pages which reference at least once a pid */ - list_for_each_entry(ml, &pf->ml, list) { - if (ml->map->pid == af->pid) - goto get_stats; - } - return; - } else if (af->pidlist && af->map) { - /* - * Find pages that reference at least once all of the - * given pids and a given mapping - */ - struct pidlist *pid; - int matches = 0; + pf = rb_to_pageframe(rb_first(root)); - /* - * Check that we reference the given mapping at least - * once - */ - list_for_each_entry(ml, &pf->ml, list) { - if (ml->map == af->map) { - matches++; - break; - } - } + while (pf) { + pages++; - if (!matches) - return; - matches = 0; + if (af->pid) { + /* Find pages which reference at least once a pid */ + list_for_each_entry(ml, &pf->ml, list) { + if (ml->map->pid == af->pid) + goto get_stats; + } + goto next; + } else if (af->pidlist && af->map) { + /* + * Find pages that reference at least once all + * of the given pids and a given mapping + */ + struct pidlist *pid; + int matches = 0; - /* - * Check that we reference all of the given pids - * too. The order of the loops is important here. We - * must scan through all the references and test for a - * given pid. If we would iterate through the - * references in the outer loop, we might get - * duplicate matches for a pid since it is possible - * that a page is mapped multiple times in a process's - * addrses space. - */ - list_for_each_entry(pid, af->pidlist, list) { + /* + * Check that we reference the given mapping + * at least once + */ list_for_each_entry(ml, &pf->ml, list) { - if (ml->map->pid == pid->pid) { + if (ml->map == af->map) { matches++; break; } } + if (!matches) + goto next; + matches = 0; + /* - * If we have found as many matches as ther - * are pids, we will count the stats + * Check that we reference all of the given + * pids too. The order of the loops is + * important here. We must scan through all + * the references and test for a given pid. If + * we would iterate through the references in + * the outer loop, we might get duplicate + * matches for a pid since it is possible that + * a page is mapped multiple times in a + * process's addrses space. */ - if (matches == af->pids) - goto get_stats; + list_for_each_entry(pid, af->pidlist, list) { + list_for_each_entry(ml, &pf->ml, list) { + if (ml->map->pid == pid->pid) { + matches++; + break; + } + } + + /* + * If we have found as many matches as ther + * are pids, we will count the stats + */ + if (matches == af->pids) + goto get_stats; + } + goto next; } - return; - } get_stats: - if (page_present(pf)) - af->pages_present++; - else if (page_swapped(pf)) - af->pages_swapped++; - if (pf->kpagecount == 1) - af->pages_unique++; - - for (i = 0; i < KPAGEFLAGS_NUM; i++) - if (kpageflag_is_set(pf, i)) - af->kpageflag[i]++; + if (page_present(pf)) + af->pages_present++; + else if (page_swapped(pf)) + af->pages_swapped++; + if (pf->kpagecount == 1) + af->pages_unique++; + + for (i = 0; i < KPAGEFLAGS_NUM; i++) + if (kpageflag_is_set(pf, i)) + af->kpageflag[i]++; + +next: + pf = rb_to_pageframe(rb_next(&pf->tree)); + } + + return pages; } /* * print_page_stats - Prints system wide page stats */ -void print_page_stats(struct pageframe *pf) +void print_page_stats(struct rb_root *root) { struct analyze_frames af; long count; int i; memset(&af, 0, sizeof(af)); - af.ops.callback = count_pages; - - count = bintree_walk(&pf->tree, &af.ops); + count = count_pages(root, &af); printf("\n"); @@ -210,7 +216,7 @@ void print_page_stats(struct pageframe *pf) PAGE_TO_NICE_UNIT(count)); } -void print_pid_stats(struct pageframe *pf, struct process *process_list, +void print_pid_stats(struct rb_root *root, struct process *process_list, struct parse_opts *opts) { struct analyze_frames af; @@ -232,10 +238,9 @@ void print_pid_stats(struct pageframe *pf, struct process *process_list, fflush(stdout); memset(&af, 0, sizeof(af)); - af.ops.callback = count_pages; af.pid = ps->pid; - bintree_walk(&pf->tree, &af.ops); + count_pages(root, &af); ps->pages_present = af.pages_present; ps->pages_swapped = af.pages_swapped; ps->pages_unique = af.pages_unique; @@ -296,7 +301,7 @@ restart: printf("Total %d processes\n", processes); } -static void _dump_process_maps(struct pageframe *pf, struct process *ps, +static void _dump_process_maps(struct rb_root *root, struct process *ps, struct parse_opts *opts) { struct maps *map; @@ -315,12 +320,11 @@ static void _dump_process_maps(struct pageframe *pf, struct process *ps, if (is_parse_option(opts, PARSE_SHARED_MAPPING)) { memset(&af, 0, sizeof(af)); - af.ops.callback = count_pages; af.pidlist = &opts->pidlist; af.pids = pids; af.map = map; - bintree_walk(&pf->tree, &af.ops); + count_pages(root, &af); map->pages_present = af.pages_present; map->pages_swapped = af.pages_swapped; } @@ -371,12 +375,12 @@ restart: printf("\n"); } -void dump_process_maps(struct pageframe *pf, struct process *process_list, +void dump_process_maps(struct rb_root *root, struct process *process_list, struct parse_opts *opts) { struct process *ps; list_for_each_entry(ps, &process_list->list, list) { - _dump_process_maps(pf, ps, opts); + _dump_process_maps(root, ps, opts); } } diff --git a/analyze.h b/analyze.h index 91bbc5d..b803e03 100644 --- a/analyze.h +++ b/analyze.h @@ -20,10 +20,10 @@ #include "pagemap.h" -void print_page_stats(struct pageframe *pf); -void print_pid_stats(struct pageframe *pf, struct process *process_list, +void print_page_stats(struct rb_root *root); +void print_pid_stats(struct rb_root *root, struct process *process_list, struct parse_opts *opts); -void dump_process_maps(struct pageframe *pf, struct process *process_list, +void dump_process_maps(struct rb_root *root, struct process *process_list, struct parse_opts *opts); #endif diff --git a/main.c b/main.c index 2142e5a..8f7f479 100644 --- a/main.c +++ b/main.c @@ -149,7 +149,7 @@ void read_args(int argc, char *argv[], struct parse_opts *opts) int main(int argc, char *argv[]) { - struct pageframe pf; + struct rb_root root; struct process process_list; struct parse_opts opts; @@ -167,26 +167,25 @@ int main(int argc, char *argv[]) opts.name = ""; } - clear_pageframe(&pf); - + memset(&root, 0, sizeof(root)); memset(&process_list, 0, sizeof(process_list)); INIT_LIST_HEAD(&process_list.list); printf("Scanning all process IDs\n"); - if (scan_all_pids(&pf, &process_list, &opts)) + if (scan_all_pids(&root, &process_list, &opts)) return 1; printf("Updating kpageflags\n"); - update_kpageflags(&pf); + update_kpageflags(&root); printf("Preparing to print out results\n"); if (opts.parse_mask & PARSE_DUMP) - dump_process_maps(&pf, &process_list, &opts); + dump_process_maps(&root, &process_list, &opts); else - print_pid_stats(&pf, &process_list, &opts); + print_pid_stats(&root, &process_list, &opts); - print_page_stats(&pf); + print_page_stats(&root); return 0; } diff --git a/pagemap.h b/pagemap.h index 34bcd75..bf431a8 100644 --- a/pagemap.h +++ b/pagemap.h @@ -19,10 +19,11 @@ #define _PAGEMAP_H #include +#include #include "utils.h" #include "list.h" -#include "bintree.h" +#include "rbtree.h" #define PAGE_SHIFT 12 #define PAGE_SIZE (1 << PAGE_SHIFT) @@ -39,7 +40,7 @@ struct maps_list { #define BITRANGE(first, last) (((2ll << (last - first)) - 1) << first) struct pageframe { - struct bintree tree; + struct rb_node tree; struct list_head ml; /* List of mappings which refer to this pfn */ unsigned long long pf; /* page frame entry from /proc/pid/pagemap */ @@ -49,7 +50,10 @@ struct pageframe { int refcount; }; -#define tree_to_pageframe(tree_struct) \ +struct pageframe *pf_insert(struct rb_root *root, struct pageframe *pf); +struct pageframe *pf_search(struct rb_root *root, struct pageframe *pf); + +#define rb_to_pageframe(tree_struct) \ container_of((tree_struct), struct pageframe, tree) static inline void clear_pageframe(struct pageframe *pf) diff --git a/parse.c b/parse.c index 97d76aa..371abdb 100644 --- a/parse.c +++ b/parse.c @@ -19,8 +19,6 @@ #include #include #include -#include -#include #include #include @@ -107,19 +105,6 @@ err: return pageframe; } -static int compare_pageframe(struct bintree *at, struct bintree *bt) -{ - struct pageframe *a, *b; - a = tree_to_pageframe(at); - b = tree_to_pageframe(bt); - - return a->pf - b->pf; -} - -struct bintree_ops pageframe_ops = { - .compare = compare_pageframe, -}; - static int pid_is_match(int pidn, struct list_head *pidlist) { struct pidlist *pid; @@ -182,7 +167,7 @@ static int should_add_to_tree(struct parse_opts *opts, struct pageframe *pf, } /* Read data from the /proc/pid/pagemap file */ -static int parse_pageframe(FILE *file, struct pageframe *pf_tree, +static int parse_pageframe(FILE *file, struct rb_root *root, struct maps *maps, struct parse_opts *opts) { struct maps *map; @@ -190,7 +175,7 @@ static int parse_pageframe(FILE *file, struct pageframe *pf_tree, struct pageframe *match, *pageframe = NULL; long start, len, i; unsigned long long pf[10240]; - int ret, error; + int ret; if (maps == NULL) return 0; @@ -205,9 +190,7 @@ static int parse_pageframe(FILE *file, struct pageframe *pf_tree, ret = fseek(file, start, SEEK_SET); if (ret) { - error = errno; - fprintf(stderr, "Error seeking to %lx: %s\n", start, - strerror(error)); + fprintf(stderr, "Error seeking to %lx: %m\n", start); continue; } @@ -217,7 +200,6 @@ static int parse_pageframe(FILE *file, struct pageframe *pf_tree, MIN(sizeof(pf), (len - i) * 8), file); } if (ret < 0) { - error = errno; continue; } if (!pageframe) @@ -235,17 +217,10 @@ static int parse_pageframe(FILE *file, struct pageframe *pf_tree, page_present(pageframe))) continue; - if (should_add_to_tree(opts, pageframe, map)) { - match = tree_to_pageframe( - bintree_add(&pf_tree->tree, - &pageframe->tree, - &pageframe_ops)); - } else { - match = tree_to_pageframe( - bintree_find(&pf_tree->tree, - &pageframe->tree, - &pageframe_ops)); - } + if (should_add_to_tree(opts, pageframe, map)) + match = pf_insert(root, pageframe); + else + match = pf_search(root, pageframe); if (match == NULL) continue; @@ -272,7 +247,7 @@ static int parse_pageframe(FILE *file, struct pageframe *pf_tree, return 0; } -static int read_pageframe(int pid, int tid, struct pageframe *pageframe, +static int read_pageframe(int pid, int tid, struct rb_root *root, struct process *process_list, struct parse_opts *opts) { struct maps *maps; @@ -306,7 +281,7 @@ static int read_pageframe(int pid, int tid, struct pageframe *pageframe, if (!file) goto free; - parse_pageframe(file, pageframe, maps, opts); + parse_pageframe(file, root, maps, opts); fclose(file); if (read_cmdline(pid, tid, process->name, sizeof(process->name))) @@ -344,7 +319,7 @@ free: } static int read_pageframe_with_threads(int pid, - struct pageframe *pageframe, + struct rb_root *root, struct process *process_list, struct parse_opts *opts) { @@ -361,8 +336,7 @@ static int read_pageframe_with_threads(int pid, if (tid <= 0) return count; - count += read_pageframe(pid, tid, pageframe, process_list, - opts); + count += read_pageframe(pid, tid, root, process_list, opts); if (!opts->with_threads) break; @@ -371,7 +345,7 @@ static int read_pageframe_with_threads(int pid, return count; } -int scan_all_pids(struct pageframe *pf, struct process *process_list, +int scan_all_pids(struct rb_root *root, struct process *process_list, struct parse_opts *opts) { struct pidlist *pidlist, *n; @@ -382,7 +356,7 @@ int scan_all_pids(struct pageframe *pf, struct process *process_list, if (is_parse_option(opts, PARSE_PID)) { list_for_each_entry_safe(pidlist, n, &opts->pidlist, list) { - count += read_pageframe_with_threads(pidlist->pid, pf, + count += read_pageframe_with_threads(pidlist->pid, root, process_list, opts); } } @@ -409,7 +383,7 @@ int scan_all_pids(struct pageframe *pf, struct process *process_list, len = printf("% 5d", pid); fflush(stdout); - read_pageframe_with_threads(pid, pf, process_list, + read_pageframe_with_threads(pid, root, process_list, opts); } @@ -432,7 +406,7 @@ int scan_all_pids(struct pageframe *pf, struct process *process_list, len = printf("% 5d", pid); fflush(stdout); - read_pageframe_with_threads(pid, pf, process_list, opts); + read_pageframe_with_threads(pid, root, process_list, opts); } for (i = 0; i < len; i++) putchar('\b'); @@ -441,77 +415,57 @@ int scan_all_pids(struct pageframe *pf, struct process *process_list, return 0; } -struct kpageflag_data { - struct bintree_ops ops; - +int update_kpageflags(struct rb_root *root) +{ + struct pageframe *pf; int kpageflags_fd; int kpagecount_fd; -}; + int ret; -#define bintree_ops_to_kpfd(bintree_ops) \ - container_of((bintree_ops), struct kpageflag_data, ops) + kpageflags_fd = open("/proc/kpageflags", O_RDONLY); + kpagecount_fd = open("/proc/kpagecount", O_RDONLY); -static void _update_kpageflags(struct bintree *bt, struct bintree_ops *ops) -{ - struct pageframe *pf = tree_to_pageframe(bt); - struct kpageflag_data *kpfd = bintree_ops_to_kpfd(ops); - int ret, error; - long int pfnn = pfn(pf) * sizeof(pf->kpageflags); - - ret = lseek(kpfd->kpageflags_fd, pfnn, SEEK_SET); - if (ret < 0) { - error = errno; - fprintf(stderr, "Error seeking to %lx: %s\n", - pfnn, strerror(error)); - return; - } + if (kpageflags_fd == -1 || kpagecount_fd == -1) + return -1; - ret = read(kpfd->kpageflags_fd, &pf->kpageflags, - sizeof(pf->kpageflags)); - if (ret < 0) { - error = errno; - fprintf(stderr, "Error reading from %llx: %s\n", - pf->pf * sizeof(pf->kpageflags), - strerror(error)); - return; - } + pf = rb_to_pageframe(rb_first(root)); - ret = lseek(kpfd->kpagecount_fd, pfnn, SEEK_SET); - if (ret < 0) { - error = errno; - fprintf(stderr, "Error seeking to %lx: %s\n", - pfnn, strerror(error)); - return; - } + while(pf) { + long int pfnn = pfn(pf) * sizeof(pf->kpageflags); - ret = read(kpfd->kpagecount_fd, &pf->kpagecount, - sizeof(pf->kpagecount)); - if (ret < 0) { - error = errno; - fprintf(stderr, "Error reading from %llx: %s\n", - pf->pf * sizeof(pf->kpagecount), - strerror(error)); - return; - } -} + ret = lseek(kpageflags_fd, pfnn, SEEK_SET); + if (ret < 0) { + fprintf(stderr, "Error seeking to %lx: %m\n", pfnn); + return -1; + } -int update_kpageflags(struct pageframe *pf) -{ - struct kpageflag_data kpfd = { - .ops = { - .callback = _update_kpageflags, - }, - .kpageflags_fd = open("/proc/kpageflags", O_RDONLY), - .kpagecount_fd = open("/proc/kpagecount", O_RDONLY), - }; - - if (kpfd.kpageflags_fd == -1 || kpfd.kpagecount_fd == -1) - return -1; + ret = read(kpageflags_fd, &pf->kpageflags, + sizeof(pf->kpageflags)); + if (ret < 0) { + fprintf(stderr, "Error reading from %llx: %m\n", + pf->pf * sizeof(pf->kpageflags)); + return -1; + } + + ret = lseek(kpagecount_fd, pfnn, SEEK_SET); + if (ret < 0) { + fprintf(stderr, "Error seeking to %lx: %m\n", pfnn); + return -1; + } - bintree_walk(&pf->tree, &kpfd.ops); + ret = read(kpagecount_fd, &pf->kpagecount, + sizeof(pf->kpagecount)); + if (ret < 0) { + fprintf(stderr, "Error reading from %llx: %m\n", + pf->pf * sizeof(pf->kpagecount)); + return -1; + } + + pf = rb_to_pageframe(rb_next(&pf->tree)); + } - close(kpfd.kpageflags_fd); - close(kpfd.kpagecount_fd); + close(kpageflags_fd); + close(kpagecount_fd); return 0; } diff --git a/parse.h b/parse.h index a9f1369..e33bb30 100644 --- a/parse.h +++ b/parse.h @@ -20,8 +20,8 @@ #include "pagemap.h" -int scan_all_pids(struct pageframe *pf, struct process *process_list, +int scan_all_pids(struct rb_root *root, struct process *process_list, struct parse_opts *opts); -int update_kpageflags(struct pageframe *pf); +int update_kpageflags(struct rb_root *root); #endif diff --git a/treeops.c b/treeops.c new file mode 100644 index 0000000..feaca58 --- /dev/null +++ b/treeops.c @@ -0,0 +1,51 @@ +#include "pagemap.h" + +struct pageframe *pf_insert(struct rb_root *root, struct pageframe *pf) +{ + struct rb_node **new = &(root->rb_node), *parent = NULL; + + /* Figure out where to put new node */ + while (*new) { + struct pageframe *this = rb_to_pageframe(*new); + int result = pf->pf - this->pf; + + parent = *new; + if (result < 0) + new = &((*new)->rb_left); + else if (result > 0) + new = &((*new)->rb_right); + else + /* + * We already have a matching node in the + * tree. Return that node to indicate the + * collision + */ + return NULL; + } + + /* Add new node and rebalance tree. */ + rb_link_node(&pf->tree, parent, new); + rb_insert_color(&pf->tree, root); + + return pf; +} + +struct pageframe *pf_search(struct rb_root *root, struct pageframe *pf) +{ + struct rb_node *node = root->rb_node; + + while (node) { + struct pageframe *this = rb_to_pageframe(node); + int result; + + result = pf->pf - this->pf; + + if (result < 0) + node = node->rb_left; + else if (result > 0) + node = node->rb_right; + else + return this; + } + return NULL; +}