bitmap.h

/*
 * Copyright (c) 2013-2017 Mellanox Technologies, Ltd.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice unmodified, this list of conditions, and the following
 *    disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef _LINUXKPI_LINUX_BITMAP_H_
#define	_LINUXKPI_LINUX_BITMAP_H_

#include <linux/bitops.h>
#include <linux/slab.h>

static inline void
bitmap_zero(unsigned long *addr, const unsigned int size)
{
	memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
}

static inline void
bitmap_fill(unsigned long *addr, const unsigned int size)
{
	const unsigned int tail = size & (BITS_PER_LONG - 1);

	memset(addr, 0xff, BIT_WORD(size) * sizeof(long));

	if (tail)
		addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
}

static inline int
bitmap_full(unsigned long *addr, const unsigned int size)
{
	const unsigned int end = BIT_WORD(size);
	const unsigned int tail = size & (BITS_PER_LONG - 1);
	unsigned int i;

	for (i = 0; i != end; i++) {
		if (addr[i] != ~0UL)
			return (0);
	}

	if (tail) {
		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);

		if ((addr[end] & mask) != mask)
			return (0);
	}
	return (1);
}

static inline int
bitmap_empty(unsigned long *addr, const unsigned int size)
{
	const unsigned int end = BIT_WORD(size);
	const unsigned int tail = size & (BITS_PER_LONG - 1);
	unsigned int i;

	for (i = 0; i != end; i++) {
		if (addr[i] != 0)
			return (0);
	}

	if (tail) {
		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);

		if ((addr[end] & mask) != 0)
			return (0);
	}
	return (1);
}

static inline void
bitmap_set(unsigned long *map, unsigned int start, int nr)
{
	const unsigned int size = start + nr;
	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);

	map += BIT_WORD(start);

	while (nr - bits_to_set >= 0) {
		*map |= mask_to_set;
		nr -= bits_to_set;
		bits_to_set = BITS_PER_LONG;
		mask_to_set = ~0UL;
		map++;
	}

	if (nr) {
		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
		*map |= mask_to_set;
	}
}

static inline void
bitmap_clear(unsigned long *map, unsigned int start, int nr)
{
	const unsigned int size = start + nr;
	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);

	map += BIT_WORD(start);

	while (nr - bits_to_clear >= 0) {
		*map &= ~mask_to_clear;
		nr -= bits_to_clear;
		bits_to_clear = BITS_PER_LONG;
		mask_to_clear = ~0UL;
		map++;
	}

	if (nr) {
		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
		*map &= ~mask_to_clear;
	}
}

static inline unsigned int
bitmap_find_next_zero_area_off(const unsigned long *map,
    const unsigned int size, unsigned int start,
    unsigned int nr, unsigned int align_mask,
    unsigned int align_offset)
{
	unsigned int index;
	unsigned int end;
	unsigned int i;

retry:
	index = find_next_zero_bit(map, size, start);

	index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;

	end = index + nr;
	if (end > size)
		return (end);

	i = find_next_bit(map, end, index);
	if (i < end) {
		start = i + 1;
		goto retry;
	}
	return (index);
}

static inline unsigned int
bitmap_find_next_zero_area(const unsigned long *map,
    const unsigned int size, unsigned int start,
    unsigned int nr, unsigned int align_mask)
{
	return (bitmap_find_next_zero_area_off(map, size,
	    start, nr, align_mask, 0));
}

static inline int
bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
{
	int pos;
	int end;

	for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
		if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
			continue;
		linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
		return (pos);
	}
	return (-ENOMEM);
}

static inline int
bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
{
	if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
		return (-EBUSY);
	linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
	return (0);
}

static inline void
bitmap_release_region(unsigned long *bitmap, int pos, int order)
{
	linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
}

static inline unsigned int
bitmap_weight(unsigned long *addr, const unsigned int size)
{
	const unsigned int end = BIT_WORD(size);
	const unsigned int tail = size & (BITS_PER_LONG - 1);
	unsigned int retval = 0;
	unsigned int i;

	for (i = 0; i != end; i++)
		retval += hweight_long(addr[i]);

	if (tail) {
		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);

		retval += hweight_long(addr[end] & mask);
	}
	return (retval);
}

static inline int
bitmap_equal(const unsigned long *pa,
    const unsigned long *pb, unsigned size)
{
	const unsigned int end = BIT_WORD(size);
	const unsigned int tail = size & (BITS_PER_LONG - 1);
	unsigned int i;

	for (i = 0; i != end; i++) {
		if (pa[i] != pb[i])
			return (0);
	}

	if (tail) {
		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);

		if ((pa[end] ^ pb[end]) & mask)
			return (0);
	}
	return (1);
}

static inline int
bitmap_subset(const unsigned long *pa,
    const unsigned long *pb, unsigned size)
{
	const unsigned end = BIT_WORD(size);
	const unsigned tail = size & (BITS_PER_LONG - 1);
	unsigned i;

	for (i = 0; i != end; i++) {
		if (pa[i] & ~pb[i])
			return (0);
	}

	if (tail) {
		const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);

		if (pa[end] & ~pb[end] & mask)
			return (0);
	}
	return (1);
}

static inline bool
bitmap_intersects(const unsigned long *pa, const unsigned long *pb,
    unsigned size)
{
	const unsigned end = BIT_WORD(size);
	const unsigned tail = size & (BITS_PER_LONG - 1);
	unsigned i;

	for (i = 0; i != end; i++)
		if (pa[i] & pb[i])
			return (true);

	if (tail) {
		 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);

		if (pa[end] & pb[end] & mask)
			return (true);
	}
	return (false);
}

static inline void
bitmap_complement(unsigned long *dst, const unsigned long *src,
    const unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	unsigned int i;

	for (i = 0; i != end; i++)
		dst[i] = ~src[i];
}

static inline void
bitmap_copy(unsigned long *dst, const unsigned long *src,
    const unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	unsigned int i;

	for (i = 0; i != end; i++)
		dst[i] = src[i];
}

static inline void
bitmap_to_arr32(uint32_t *dst, const unsigned long *src, unsigned int size)
{
	const unsigned int end = howmany(size, 32);

#ifdef __LP64__
	unsigned int i = 0;
	while (i < end) {
		dst[i++] = (uint32_t)(*src & UINT_MAX);
		if (i < end)
			dst[i++] = (uint32_t)(*src >> 32);
		src++;
	}
#else
	bitmap_copy((unsigned long *)dst, src, size);
#endif
	if ((size % 32) != 0) /* Linux uses BITS_PER_LONG. Seems to be a bug */
		dst[end - 1] &= (uint32_t)(UINT_MAX >> (32 - (size % 32)));
}

static inline void
bitmap_from_arr32(unsigned long *dst, const uint32_t *src,
    unsigned int size)
{
	const unsigned int end = BIT_WORD(size);
	const unsigned int tail = size & (BITS_PER_LONG - 1);

#ifdef __LP64__
	const unsigned int end32 = howmany(size, 32);
	unsigned int i = 0;

	while (i < end32) {
		dst[i++/2] = (unsigned long) *(src++);
		if (i < end32)
			dst[i++/2] |= ((unsigned long) *(src++)) << 32;
	}
#else
	bitmap_copy(dst, (const unsigned long *)src, size);
#endif
	if ((size % BITS_PER_LONG) != 0)
		dst[end] &= BITMAP_LAST_WORD_MASK(tail);
}

static inline void
bitmap_or(unsigned long *dst, const unsigned long *src1,
    const unsigned long *src2, const unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	unsigned int i;

	for (i = 0; i != end; i++)
		dst[i] = src1[i] | src2[i];
}

static inline void
bitmap_and(unsigned long *dst, const unsigned long *src1,
    const unsigned long *src2, const unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	unsigned int i;

	for (i = 0; i != end; i++)
		dst[i] = src1[i] & src2[i];
}

static inline void
bitmap_andnot(unsigned long *dst, const unsigned long *src1,
    const unsigned long *src2, const unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	unsigned int i;

	for (i = 0; i != end; i++)
		dst[i] = src1[i] & ~src2[i];
}

static inline void
bitmap_xor(unsigned long *dst, const unsigned long *src1,
    const unsigned long *src2, const unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	unsigned int i;

	for (i = 0; i != end; i++)
		dst[i] = src1[i] ^ src2[i];
}

static inline void
bitmap_shift_right(unsigned long *dst, const unsigned long *src,
    unsigned int shift, unsigned int size)
{
	const unsigned int end = BITS_TO_LONGS(size);
	const unsigned int tail = size & (BITS_PER_LONG - 1);
	const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
	const unsigned int off = BIT_WORD(shift);
	const unsigned int rem = shift & (BITS_PER_LONG - 1);
	unsigned long left, right;
	unsigned int i, srcpos;

	for (i = 0, srcpos = off; srcpos < end; i++, srcpos++) {
		right = src[srcpos];
		left = 0;

		if (srcpos == end - 1)
			right &= mask;

		if (rem != 0) {
			right >>= rem;
			if (srcpos + 1 < end) {
				left = src[srcpos + 1];
				if (srcpos + 1 == end - 1)
					left &= mask;
				left <<= (BITS_PER_LONG - rem);
			}
		}
		dst[i] = left | right;
	}
	if (off != 0)
		memset(dst + end - off, 0, off * sizeof(unsigned long));
}

static inline unsigned long *
bitmap_alloc(unsigned int size, gfp_t flags)
{
	return (kmalloc_array(BITS_TO_LONGS(size),
	    sizeof(unsigned long), flags));
}

static inline unsigned long *
bitmap_zalloc(unsigned int size, gfp_t flags)
{
	return (bitmap_alloc(size, flags | __GFP_ZERO));
}

static inline void
bitmap_free(const unsigned long *bitmap)
{
	kfree(bitmap);
}

#endif					/* _LINUXKPI_LINUX_BITMAP_H_ */