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))
#include "analyze.h"
#include "utils.h"
-#include "bintree.h"
struct kpageflag_str kpageflag_str[] = {
{ .flag = LOCKED, .str = "locked", },
#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;
#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");
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;
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;
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;
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;
}
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);
}
}
#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
int main(int argc, char *argv[])
{
- struct pageframe pf;
+ struct rb_root root;
struct process process_list;
struct parse_opts opts;
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;
}
#define _PAGEMAP_H
#include <stdlib.h>
+#include <string.h>
#include "utils.h"
#include "list.h"
-#include "bintree.h"
+#include "rbtree.h"
#define PAGE_SHIFT 12
#define PAGE_SIZE (1 << PAGE_SHIFT)
#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 */
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)
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
-#include <string.h>
-#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
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;
}
/* 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;
struct pageframe *match, *pageframe = NULL;
long start, len, i;
unsigned long long pf[10240];
- int ret, error;
+ int ret;
if (maps == NULL)
return 0;
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;
}
MIN(sizeof(pf), (len - i) * 8), file);
}
if (ret < 0) {
- error = errno;
continue;
}
if (!pageframe)
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;
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;
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)))
}
static int read_pageframe_with_threads(int pid,
- struct pageframe *pageframe,
+ struct rb_root *root,
struct process *process_list,
struct parse_opts *opts)
{
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;
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;
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);
}
}
len = printf("% 5d", pid);
fflush(stdout);
- read_pageframe_with_threads(pid, pf, process_list,
+ read_pageframe_with_threads(pid, root, process_list,
opts);
}
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');
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;
}
#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
--- /dev/null
+#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;
+}
projects / scan-pagemap / commitdiff