1/*
 2 * xvmalloc memory allocator
 3 *
 4 * Copyright (C) 2008, 2009, 2010  Nitin Gupta
 5 *
 6 * This code is released using a dual license strategy: BSD/GPL
 7 * You can choose the licence that better fits your requirements.
 8 *
 9 * Released under the terms of 3-clause BSD License
10 * Released under the terms of GNU General Public License Version 2.0
11 */
12
13#ifndef _XV_MALLOC_INT_H_
14#define _XV_MALLOC_INT_H_
15
16#include <linux/kernel.h>
17#include <linux/types.h>
18
19/* User configurable params */
20
21/* Must be power of two */
22#ifdef CONFIG_64BIT
23#define XV_ALIGN_SHIFT 3
24#else
25#define XV_ALIGN_SHIFT	2
26#endif
27#define XV_ALIGN	(1 << XV_ALIGN_SHIFT)
28#define XV_ALIGN_MASK	(XV_ALIGN - 1)
29
30/* This must be greater than sizeof(link_free) */
31#define XV_MIN_ALLOC_SIZE	32
32#define XV_MAX_ALLOC_SIZE	(PAGE_SIZE - XV_ALIGN)
33
34/*
35 * Free lists are separated by FL_DELTA bytes
36 * This value is 3 for 4k pages and 4 for 64k pages, for any
37 * other page size, a conservative (PAGE_SHIFT - 9) is used.
38 */
39#if PAGE_SHIFT == 16
40#define FL_DELTA_SHIFT 4
41#else
42#define FL_DELTA_SHIFT (PAGE_SHIFT - 9)
43#endif
44#define FL_DELTA	(1 << FL_DELTA_SHIFT)
45#define FL_DELTA_MASK	(FL_DELTA - 1)
46#define NUM_FREE_LISTS	((XV_MAX_ALLOC_SIZE - XV_MIN_ALLOC_SIZE) \
47				/ FL_DELTA + 1)
48
49#define MAX_FLI		DIV_ROUND_UP(NUM_FREE_LISTS, BITS_PER_LONG)
50
51/* End of user params */
52
53enum blockflags {
54	BLOCK_FREE,
55	PREV_FREE,
56	__NR_BLOCKFLAGS,
57};
58
59#define FLAGS_MASK	XV_ALIGN_MASK
60#define PREV_MASK	(~FLAGS_MASK)
61
62struct freelist_entry {
63	struct page *page;
64	u16 offset;
65	u16 pad;
66};
67
68struct link_free {
69	struct page *prev_page;
70	struct page *next_page;
71	u16 prev_offset;
72	u16 next_offset;
73};
74
75struct block_header {
76	union {
77		/* This common header must be XV_ALIGN bytes */
78		u8 common[XV_ALIGN];
79		struct {
80			u16 size;
81			u16 prev;
82		};
83	};
84	struct link_free link;
85};
86
87struct xv_pool {
88	ulong flbitmap;
89	ulong slbitmap[MAX_FLI];
90	u64 total_pages;	/* stats */
91	struct freelist_entry freelist[NUM_FREE_LISTS];
92	spinlock_t lock;
93};
94
95#endif