diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am
index 999a7f5..5b38c7b 100644
--- a/platform/linux-generic/Makefile.am
+++ b/platform/linux-generic/Makefile.am
@@ -130,6 +130,7 @@ noinst_HEADERS = \
 		  ${srcdir}/include/odp_align_internal.h \
 		  ${srcdir}/include/odp_atomic_internal.h \
 		  ${srcdir}/include/odp_buffer_inlines.h \
+		  ${srcdir}/include/odp_bitmap_internal.h \
 		  ${srcdir}/include/odp_buffer_internal.h \
 		  ${srcdir}/include/odp_classification_datamodel.h \
 		  ${srcdir}/include/odp_classification_inlines.h \
@@ -173,6 +174,7 @@ __LIB__libodp_linux_la_SOURCES = \
 			   _ishmphy.c \
 			   odp_atomic.c \
 			   odp_barrier.c \
+			   odp_bitmap.c \
 			   odp_buffer.c \
 			   odp_byteorder.c \
 			   odp_classification.c \
diff --git a/platform/linux-generic/include/odp_bitmap_internal.h b/platform/linux-generic/include/odp_bitmap_internal.h
new file mode 100644
index 0000000..1be4d02
--- /dev/null
+++ b/platform/linux-generic/include/odp_bitmap_internal.h
@@ -0,0 +1,317 @@
+/* Copyright (c) 2016, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier:     BSD-3-Clause
+ */
+
+/**
+ * @file
+ *
+ * ODP generic bitmap types and operations.
+ */
+
+#ifndef ODP_BITMAP_INTERNAL_H_
+#define ODP_BITMAP_INTERNAL_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <string.h>
+#include <odp/api/hints.h>
+
+/* Generate unique identifier for instantiated class */
+#define TOKENIZE(template, line) \
+	template ## _ ## line ## _ ## __COUNTER__
+
+/* Array size in general */
+#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
+
+#define BITS_PER_BYTE	(8)
+#define BITS_PER_LONG	__WORDSIZE
+#define BYTES_PER_LONG	(BITS_PER_LONG / BITS_PER_BYTE)
+
+#define BIT_WORD(nr)	((nr) / BITS_PER_LONG)
+#define BITS_TO_LONGS(nr) BIT_WORD(nr + BITS_PER_LONG - 1)
+
+#define BITMAP_FIRST_WORD_MASK(start) \
+	(~0UL << ((start) & (BITS_PER_LONG - 1)))
+#define BITMAP_LAST_WORD_MASK(nbits)  \
+	(~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
+
+/* WAPL bitmap base class */
+typedef struct {
+	unsigned int  nwords;
+	unsigned int  *pl;
+	unsigned long *ul;
+} wapl_bitmap_t;
+
+/*
+ * Word-Aligned Position List (WAPL) bitmap, which actually
+ * is not a compression, but with an extra list of non-empty
+ * word positions.
+ *
+ * WAPL accelerates bitwise operations and iterations by
+ * applying only to non-empty positions instead of walking
+ * through the whole bitmap.
+ *
+ * WAPL uses [1 ~ N] instead of [0 ~ N - 1] as position
+ * values and an extra 0 as end indicator for position list.
+ * This is the reason to allocate one extra room below.
+ */
+#define instantiate_wapl_bitmap(line, nbits)			\
+	struct TOKENIZE(wapl_bitmap, line) {			\
+		unsigned int pl[BITS_TO_LONGS(nbits) + 1];	\
+		unsigned long ul[BITS_TO_LONGS(nbits) + 1];	\
+	}
+
+#define WAPL_BITMAP(nbits) instantiate_wapl_bitmap(__LINE__, nbits)
+
+/*
+ * Upcast any derived WAPL bitmap class to its base class
+ */
+#define __wapl_upcast(base, derived)				\
+	do {							\
+		__typeof__(derived) p = derived;		\
+		base.pl = p->pl;				\
+		base.ul = p->ul;				\
+		base.nwords = ARRAY_SIZE(p->ul) - 1;		\
+	} while (0)
+
+/*
+ * WAPL base class bitmap operations
+ */
+void __wapl_bitmap_and(wapl_bitmap_t *dst,
+		       wapl_bitmap_t *src, wapl_bitmap_t *and);
+
+void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or);
+
+void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit);
+
+void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit);
+
+/*
+ * Generic WAPL bitmap operations
+ */
+#define wapl_bitmap_zero(map)					\
+	({							\
+		__typeof__(map) p = map;			\
+		memset((void *)p, 0, sizeof(__typeof__(*p)));	\
+	})
+
+#define wapl_bitmap_copy(dst, src)				\
+	({							\
+		__typeof__(dst) d = dst;			\
+		__typeof__(src) s = src;			\
+		if (d != s)					\
+			memcpy((void *)d, (void *)s,		\
+				sizeof(__typeof__(*d)));	\
+	})
+
+#define wapl_bitmap_and(dst, src, and)				\
+	({							\
+		wapl_bitmap_t d, s, a;				\
+		__wapl_upcast(d, dst);				\
+		__wapl_upcast(s, src);				\
+		__wapl_upcast(a, and);				\
+		__wapl_bitmap_and(&d, &s, &a);			\
+	})
+
+#define wapl_bitmap_or(dst, src, or)				\
+	({							\
+		wapl_bitmap_t d, o;				\
+		wapl_bitmap_copy(dst, src);			\
+		__wapl_upcast(d, dst);				\
+		__wapl_upcast(o, or);				\
+		__wapl_bitmap_or(&d, &o);			\
+	})
+
+#define wapl_bitmap_set(map, bit)				\
+	({							\
+		wapl_bitmap_t b;				\
+		__wapl_upcast(b, map);				\
+		__wapl_bitmap_set(&b, bit);			\
+	})
+
+#define wapl_bitmap_clear(map, bit)				\
+	({							\
+		wapl_bitmap_t b;				\
+		__wapl_upcast(b, map);				\
+		__wapl_bitmap_clear(&b, bit);			\
+	})
+
+/*
+ * Round robin iterator runs upon a WAPL bitmap:
+ *
+ * wapl_bitmap_iterator(iterator, WAPL bitmap);
+ * for (iterator->start(); iterator->has_next(); ) {
+ *	unsigned int bit_index = iterator->next();
+ *	...operations on this bit index...
+ * }
+ */
+typedef struct wapl_bitmap_iterator {
+	int _start, _next, _nbits;
+	wapl_bitmap_t _base;
+
+	void (*start)(struct wapl_bitmap_iterator *this);
+	bool (*has_next)(struct wapl_bitmap_iterator *this);
+	unsigned int (*next)(struct wapl_bitmap_iterator *this);
+} wapl_bitmap_iterator_t;
+
+/*
+ * WAPL bitmap iterator constructor
+ */
+void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this);
+
+/*
+ * Generic constructor accepts any derived WAPL bitmap class
+ */
+#define wapl_bitmap_iterator(iterator, map)			\
+	({							\
+		__typeof__(iterator) __it = iterator;		\
+		__wapl_upcast(__it->_base, map);		\
+		__wapl_bitmap_iterator(__it);			\
+	})
+
+/* Sparse bitmap base class */
+typedef struct {
+	unsigned int nbits;
+	unsigned int *last, *pl, *il;
+} sparse_bitmap_t;
+
+/*
+ * Sparse bitmap, lists all bit indexes directly as an array.
+ * Expected to be significantly straightforward iteration.
+ */
+#define instantiate_sparse_bitmap(line, nbits)			\
+	struct TOKENIZE(sparse_bitmap, line) {			\
+		unsigned int last;				\
+		unsigned int pl[nbits];				\
+		unsigned int il[nbits];				\
+	}
+
+#define SPARSE_BITMAP(nbits) instantiate_sparse_bitmap(__LINE__, nbits)
+
+/*
+ * Upcast any derived sparse bitmap class to its base class
+ */
+#define __sparse_upcast(base, derived)				\
+	do {							\
+		__typeof__(derived) p = derived;		\
+		base.pl = p->pl;				\
+		base.il = p->il;				\
+		base.last = &p->last;				\
+		base.nbits = ARRAY_SIZE(p->il);			\
+	} while (0)
+
+/*
+ * Sparse base class bitmap operations
+ */
+void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit);
+
+void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit);
+
+/*
+ * Generic sparse bitmap operations
+ */
+#define sparse_bitmap_zero(map)					\
+	({							\
+		__typeof__(map) p = map;			\
+		memset((void *)p, 0, sizeof(__typeof__(*p)));	\
+	})
+
+#define sparse_bitmap_set(map, bit)				\
+	({							\
+		sparse_bitmap_t b;				\
+		__sparse_upcast(b, map);			\
+		__sparse_bitmap_set(&b, bit);			\
+	})
+
+#define sparse_bitmap_clear(map, bit)				\
+	({							\
+		sparse_bitmap_t b;				\
+		__sparse_upcast(b, map);			\
+		__sparse_bitmap_clear(&b, bit);			\
+	})
+
+/*
+ * Round robin iterator runs upon a sparse bitmap:
+ *
+ * sparse_bitmap_iterator(iterator, SPARSE bitmap);
+ * for (iterator->start(); iterator->has_next(); ) {
+ *	unsigned int bit_index = iterator->next();
+ *	...operations on this bit index...
+ * }
+ */
+typedef struct sparse_bitmap_iterator {
+	int _start, _next, _nbits;
+	sparse_bitmap_t _base;
+
+	void (*start)(struct sparse_bitmap_iterator *this);
+	bool (*has_next)(struct sparse_bitmap_iterator *this);
+	unsigned int (*next)(struct sparse_bitmap_iterator *this);
+} sparse_bitmap_iterator_t;
+
+/*
+ * Sparse bitmap iterator constructor
+ */
+void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this);
+
+/*
+ * Generic constructor accepts any derived sparse bitmap class.
+ */
+#define sparse_bitmap_iterator(iterator, map)			\
+	({							\
+		__typeof__(iterator) __it = iterator;		\
+		__sparse_upcast(__it->_base, map);		\
+		__sparse_bitmap_iterator(__it);			\
+	})
+
+/*
+ * Raw bitmap atomic set and clear.
+ */
+void raw_bitmap_set(unsigned long *map, unsigned int bit);
+
+void raw_bitmap_clear(unsigned long *map, unsigned int bit);
+
+/*
+ * It will enter infinite loop incase that all bits are zero,
+ * so please make sure the bitmap at least has one set.
+ */
+static inline int __bitmap_wraparound_next(
+	unsigned long *addr, unsigned int nbits, int start)
+{
+	unsigned long tmp;
+
+	if (start >= (int)nbits)
+		start = 0;
+
+	tmp = addr[BIT_WORD(start)];
+
+	/* Handle 1st word. */
+	tmp &= BITMAP_FIRST_WORD_MASK(start);
+	start = start & ~(BITS_PER_LONG - 1);
+
+	while (!tmp) {
+		start += BITS_PER_LONG;
+		if (start >= (int)nbits)
+			start = 0;
+
+		tmp = addr[BIT_WORD(start)];
+	}
+
+	start += __builtin_ffsl(tmp) - 1;
+	return start;
+}
+
+/**
+ * @}
+ */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/platform/linux-generic/odp_bitmap.c b/platform/linux-generic/odp_bitmap.c
new file mode 100644
index 0000000..a29b9ef
--- /dev/null
+++ b/platform/linux-generic/odp_bitmap.c
@@ -0,0 +1,315 @@
+/* Copyright (c) 2016, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier:     BSD-3-Clause
+ */
+
+#include <string.h>
+#include <unistd.h>
+#include <odp/api/std_types.h>
+#include <odp/api/byteorder.h>
+#include <odp_bitmap_internal.h>
+
+/*
+ * WAPL base class bitmap operations
+ */
+static inline void __wapl_add_pos(
+	wapl_bitmap_t *map, unsigned int p)
+{
+	unsigned int s, k = 0;
+	unsigned int *pl = map->pl;
+
+	while (pl[k] && p > pl[k])
+		k++;
+
+	if (p == pl[k])
+		return;
+
+	/* sorted insertion */
+	for (; pl[k] && p < pl[k]; k++) {
+		s = pl[k];
+		pl[k] = p;
+		p = s;
+	}
+
+	if (k < map->nwords)
+		pl[k++] = p;
+
+	pl[k] = 0;
+}
+
+static inline void __wapl_remove_pos(
+	wapl_bitmap_t *map, unsigned int p)
+{
+	unsigned int k = 0;
+	unsigned int *pl = map->pl;
+
+	while (pl[k] && p != pl[k])
+		k++;
+
+	for (; pl[k]; k++)
+		pl[k] = pl[k + 1];
+}
+
+void __wapl_bitmap_and(wapl_bitmap_t *dst,
+		       wapl_bitmap_t *src, wapl_bitmap_t *and)
+{
+	unsigned int k = 0, p;
+	unsigned int *pl = src->pl;
+
+	while ((p = *pl++) != 0) {
+		dst->ul[p] = src->ul[p] & and->ul[p];
+		if (dst->ul[p])
+			dst->pl[k++] = p;
+	}
+
+	dst->pl[k] = 0;
+}
+
+void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or)
+{
+	unsigned int p;
+	unsigned int *pl = or->pl;
+
+	while ((p = *pl++) != 0) {
+		if (dst->ul[p] == 0)
+			__wapl_add_pos(dst, p);
+
+		dst->ul[p] |= or->ul[p];
+	}
+}
+
+void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit)
+{
+	unsigned int p = BIT_WORD(bit) + 1;
+	unsigned long set = 1UL << (bit & (BITS_PER_LONG - 1));
+
+	if (p > map->nwords)
+		return;
+
+	if (map->ul[p] == 0)
+		__wapl_add_pos(map, p);
+
+	map->ul[p] |= set;
+}
+
+void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit)
+{
+	unsigned int p = BIT_WORD(bit) + 1;
+	unsigned long clear = 1UL << (bit & (BITS_PER_LONG - 1));
+
+	if (p > map->nwords)
+		return;
+
+	map->ul[p] &= ~clear;
+
+	if (map->ul[p] == 0)
+		__wapl_remove_pos(map, p);
+}
+
+/*
+ * WAPL bitmap iterator implementation
+ */
+static void __wapl_iterator_start(wapl_bitmap_iterator_t *this)
+{
+	this->_nbits = this->_base.nwords * BITS_PER_LONG;
+
+	/* Advance to next queue index to start this
+	 * new round iteration.
+	 */
+	if (this->_base.pl[0] == 0)
+		this->_start = -1;
+	else
+		this->_start = __bitmap_wraparound_next(
+			&this->_base.ul[1], this->_nbits, this->_start + 1);
+
+	this->_next = this->_start;
+}
+
+static bool __wapl_iterator_has_next(wapl_bitmap_iterator_t *this)
+{
+	return (this->_next != -1);
+}
+
+static unsigned int __wapl_iterator_next(wapl_bitmap_iterator_t *this)
+{
+	int next = this->_next;
+
+	this->_next = __bitmap_wraparound_next(
+			&this->_base.ul[1], this->_nbits, this->_next + 1);
+
+	if (this->_next == this->_start)
+		this->_next = -1;
+
+	return next;
+}
+
+void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this)
+{
+	this->start = __wapl_iterator_start;
+	this->has_next = __wapl_iterator_has_next;
+	this->next = __wapl_iterator_next;
+
+	this->_start = -1;
+	this->_next = this->_start;
+}
+
+/*
+ * Sparse base class bitmap operations
+ */
+void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit)
+{
+	unsigned int last = *map->last;
+
+	/* Index exceeds */
+	if (bit >= map->nbits)
+		return;
+
+	/* Full bitmap */
+	if (last >= map->nbits)
+		return;
+
+	/* Bit was not set previously,
+	 * also record where we set the bit
+	 */
+	if (!map->pl[bit]) {
+		map->il[last++] = bit;
+		map->pl[bit] = last;
+
+		*map->last = last;
+	}
+}
+
+void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit)
+{
+	unsigned int p, i;
+	unsigned int last = *map->last;
+
+	/* Index exceeds */
+	if (bit >= map->nbits)
+		return;
+
+	/* Empty bitmap */
+	if (last == 0)
+		return;
+
+	/* Bit was set previously */
+	if (map->pl[bit]) {
+		p = map->pl[bit] - 1;
+		map->pl[bit] = 0;
+
+		last--;
+		*map->last = last;
+
+		/* Fill the hole with the latest index */
+		if (p < last) {
+			i = map->il[last];
+			map->pl[i] = p + 1;
+			map->il[p] = i;
+		}
+	}
+}
+
+/*
+ * Sparse bitmap iterator implementation
+ */
+static void __sparse_iterator_start(sparse_bitmap_iterator_t *this)
+{
+	this->_nbits = (int)*this->_base.last;
+
+	/* Advance to next queue index to start this
+	 * new round iteration.
+	 */
+	if (this->_nbits == 0)
+		this->_start = -1;
+	else
+		this->_start = (this->_start + 1) & (this->_nbits - 1);
+
+	this->_next = this->_start;
+}
+
+static bool __sparse_iterator_has_next(sparse_bitmap_iterator_t *this)
+{
+	return (this->_next != -1);
+}
+
+static unsigned int __sparse_iterator_next(sparse_bitmap_iterator_t *this)
+{
+	int next = this->_next;
+
+	this->_next = (this->_next + 1) & (this->_nbits - 1);
+	if (this->_next == this->_start)
+		this->_next = -1;
+
+	return this->_base.il[next];
+}
+
+void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this)
+{
+	this->start = __sparse_iterator_start;
+	this->has_next = __sparse_iterator_has_next;
+	this->next = __sparse_iterator_next;
+
+	this->_start = -1;
+	this->_next = this->_start;
+}
+
+/*
+ * Generic byte-width atomic set/clear
+ */
+static inline void atomic_byte_set(
+	unsigned char *addr, unsigned int bit)
+{
+	unsigned char load, store;
+	unsigned char set = 1 << (bit & (BITS_PER_BYTE - 1));
+
+	do {
+		load = *addr;
+		store = load | set;
+	} while (!__atomic_compare_exchange_n(addr, &load, store,
+			0, __ATOMIC_RELEASE, __ATOMIC_RELAXED));
+}
+
+static inline void atomic_byte_clear(
+	unsigned char *addr, unsigned int bit)
+{
+	unsigned char load, store;
+	unsigned char clear = 1 << (bit & (BITS_PER_BYTE - 1));
+
+	do {
+		load = *addr;
+		store = load & ~clear;
+	} while (!__atomic_compare_exchange_n(addr, &load, store,
+			0, __ATOMIC_RELEASE, __ATOMIC_RELAXED));
+}
+
+static inline unsigned char *__bit_byte(
+	unsigned long *word, unsigned int bit)
+{
+	unsigned int i;
+	unsigned char *b;
+
+	b = (unsigned char *)word;
+
+	i = bit & (BITS_PER_LONG - 1);
+	i = i / BITS_PER_BYTE;
+
+#if (ODP_BYTE_ORDER == ODP_BIG_ENDIAN)
+	i = BYTES_PER_LONG - 1 - i;
+#endif
+	return &b[i];
+}
+
+void raw_bitmap_set(unsigned long *map, unsigned int bit)
+{
+	unsigned long *p = map + BIT_WORD(bit);
+
+	atomic_byte_set(__bit_byte(p, bit), bit);
+}
+
+void raw_bitmap_clear(unsigned long *map, unsigned int bit)
+{
+	unsigned long *p = map + BIT_WORD(bit);
+
+	atomic_byte_clear(__bit_byte(p, bit), bit);
+}
