/*
 * linux/fs/proc/nodemem.c
 *
 * Copyright (C) 2004 Per Ekman (pek@pdc.kth.se)
 * Development supported by AMD.
 * 
 * This file is released under the GPL.
 * 
 * Per-process proc device to map virtual memory to nodes.
 * 
 */

#include <linux/errno.h>
#include <linux/proc_fs.h>
#include <linux/kernel.h>
#include <linux/mmzone.h>
#include <linux/mm.h>
#include <linux/seq_file.h>
#include <linux/sched.h>
#include <linux/threads.h>

/* Offsets into the range list array.  If the range_list array is
 * extended, make sure NOT_PRESENT remains the size of it.  */
#define NOT_PRESENT NR_CPUS

#define RP_ENTRY_SIZE (2*(sizeof(unsigned long)))
#define RP_MAX_ENTRIES ((PAGE_SIZE / RP_ENTRY_SIZE) - 1)

#define RP_START(p, i) (p->v[i*2])
#define RP_END(p, i) (p->v[i*2 + 1])
#define RP_ISEMPTY(p, i) ((p->v[i*2] == 0) && (p->v[i*2 + 1] == 0))

struct range_page {
	unsigned long count;
	unsigned long v[2 * RP_MAX_ENTRIES] __attribute__ ((packed));
	struct range_page *next __attribute__ ((packed));
};

struct range_list {
	struct range_page *rp;
	unsigned long *cache;
};

static inline int mergeable_range(unsigned long a, unsigned long b,
				  unsigned long x, unsigned long y)
{
	if (a < x) {
		if (b >= x - 1)
			return 1;
	} else if (a <= y + 1)
		return 1;

	return 0;
}

static inline void join_pair(unsigned long *v, unsigned long start,
			     unsigned long end)
{
	if (start < v[0])
		v[0] = start;
	if (end > v[1])
		v[1] = end;
}

static inline struct range_page *grow_rp(struct range_page *rp)
{
	struct range_page *p;

	if (rp == NULL)
		p = rp;
	else
		p = rp->next;
	if ((p = (struct range_page *)__get_free_page(GFP_KERNEL)) == NULL)
		return NULL;
	memset(p, 0, PAGE_SIZE);

	return p;
}

static void free_rl(struct range_list *rlp)
{
	struct range_page *p, *rp = rlp->rp;

	while (rp) {
		p = rp;
		rp = rp->next;
		free_page((unsigned long)p);
	}
}

static void insert_rl(struct range_list *rlp, unsigned long start,
		      unsigned long end)
{
	struct range_page *rp, *p = NULL;
	unsigned long *empty = NULL;
	int i;

	if (rlp->cache &&
	    mergeable_range(start, end, rlp->cache[0], rlp->cache[1])) {
		join_pair(rlp->cache, start, end);
		return;
	}
	rp = rlp->rp;
	while (rp) {
		p = rp;
		for (i = 0; i < p->count; i++) {
			if (RP_ISEMPTY(p, i)) {
				if (empty == NULL)
					empty = &RP_START(p, i);
			} else if (mergeable_range(start, end, RP_START(p, i),
						   RP_END(p, i))) {
				join_pair(&RP_START(p, i), start, end);
				rlp->cache = &RP_START(p, i);
				return;
			}
		}
		rp = rp->next;
	}

	/* No hit */
	if (empty) {
		empty[0] = start;
		empty[1] = end;
		return;
	}
	if (!p || p->count == RP_MAX_ENTRIES)
		p = grow_rp(p);
	if (!rlp->rp)
		rlp->rp = p;
	RP_START(p, p->count) = start;
	RP_END(p, p->count) = end;
	rlp->cache = &RP_START(p, p->count);
	p->count++;
}

static inline int page2node(struct page *page)
{
	struct zone *zone = page_zone(page);
	return zone->zone_pgdat->node_id;
}

int nodemem_show(struct seq_file *s, void *v)
{
	struct range_list *rlp;
	struct range_page *rp;
	struct task_struct *task = s->private;
	struct vm_area_struct *vma;
	pgd_t *pgd;
	pmd_t *pmd;
	pte_t *ptep, pte;
	unsigned long pga;
	int n, i;

	long node_pgc[NOT_PRESENT + 1];

	rlp = kmalloc((sizeof *rlp) * (NOT_PRESENT + 1), GFP_KERNEL);
	if (!rlp)
		return 1;
	memset(rlp, 0, (sizeof *rlp) * (NOT_PRESENT + 1));

	for (n = 0; n <= NOT_PRESENT; n++)
		node_pgc[n] = 0;
	down_read(&task->active_mm->mmap_sem);
	/* For each VMA, translate each page it spans to a node number */
	for (vma = task->active_mm->mmap; vma; vma = vma->vm_next) {
		for (pga = PAGE_ALIGN(vma->vm_start); pga < vma->vm_end;
		     pga += PAGE_SIZE) {
			n = NOT_PRESENT;
			pgd = pgd_offset(task->active_mm, pga);
			if (pgd_none(*pgd) || pgd_bad(*pgd))
				goto out;
			pmd = pmd_offset(pgd, pga);
			if (pmd_none(*pmd) || pmd_bad(*pmd))
				goto out;
			ptep = pte_offset_map(pmd, pga);
			if (!ptep)
				goto out;
			pte = *ptep;
			pte_unmap(ptep);
			n = page2node(pte_page(pte));
		      out:
			node_pgc[n]++;
			insert_rl(&rlp[n], pga, pga + PAGE_SIZE - 1);
		}
	}
	up_read(&task->active_mm->mmap_sem);
	for (n = 0; n <= NOT_PRESENT; n++) {
		for (rp = rlp[n].rp; rp; rp = rp->next) {
			for (i = 0; i < rp->count; i++) {
				if (RP_ISEMPTY(rp, i))
					continue;
				if (n == NOT_PRESENT)
					seq_printf(s,
						   "%016lx-%016lx not "
						   "present\n",
						   RP_START(rp, i),
						   RP_END(rp, i));
				else
					seq_printf(s, "%016lx-%016lx node %d\n",
						   RP_START(rp, i),
						   RP_END(rp, i), n);

			}
		}
	}
	seq_printf(s, "Process running on node %d\n", task->thread_info->cpu);
	for (n = 0; n <= NOT_PRESENT; n++) {
		if (n == NOT_PRESENT)
			seq_printf(s, "Process has %ld bytes (%ld pages) "
				   "not in core\n",
				   node_pgc[n] * PAGE_SIZE, node_pgc[n]);
		else
			seq_printf(s, "Process has %ld bytes (%ld pages)"
				   " on node %d\n",
				   node_pgc[n] * PAGE_SIZE, node_pgc[n], n);
	}

	for (n = 0; n <= NOT_PRESENT; n++)
		free_rl(&rlp[n]);

	return 0;
}