cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

bitext.c (2951B)

      1// SPDX-License-Identifier: GPL-2.0
      2/*
      3 * bitext.c: kernel little helper (of bit shuffling variety).
      4 *
      5 * Copyright (C) 2002 Pete Zaitcev <zaitcev@yahoo.com>
      6 *
      7 * The algorithm to search a zero bit string is geared towards its application.
      8 * We expect a couple of fixed sizes of requests, so a rotating counter, reset
      9 * by align size, should provide fast enough search while maintaining low
     10 * fragmentation.
     11 */
     12
     13#include <linux/string.h>
     14#include <linux/bitmap.h>
     15
     16#include <asm/bitext.h>
     17
     18/**
     19 * bit_map_string_get - find and set a bit string in bit map.
     20 * @t: the bit map.
     21 * @len: requested string length
     22 * @align: requested alignment
     23 *
     24 * Returns offset in the map or -1 if out of space.
     25 *
     26 * Not safe to call from an interrupt (uses spin_lock).
     27 */
     28int bit_map_string_get(struct bit_map *t, int len, int align)
     29{
     30	int offset, count;	/* siamese twins */
     31	int off_new;
     32	int align1;
     33	int i, color;
     34
     35	if (t->num_colors) {
     36		/* align is overloaded to be the page color */
     37		color = align;
     38		align = t->num_colors;
     39	} else {
     40		color = 0;
     41		if (align == 0)
     42			align = 1;
     43	}
     44	align1 = align - 1;
     45	if ((align & align1) != 0)
     46		BUG();
     47	if (align < 0 || align >= t->size)
     48		BUG();
     49	if (len <= 0 || len > t->size)
     50		BUG();
     51	color &= align1;
     52
     53	spin_lock(&t->lock);
     54	if (len < t->last_size)
     55		offset = t->first_free;
     56	else
     57		offset = t->last_off & ~align1;
     58	count = 0;
     59	for (;;) {
     60		off_new = find_next_zero_bit(t->map, t->size, offset);
     61		off_new = ((off_new + align1) & ~align1) + color;
     62		count += off_new - offset;
     63		offset = off_new;
     64		if (offset >= t->size)
     65			offset = 0;
     66		if (count + len > t->size) {
     67			spin_unlock(&t->lock);
     68/* P3 */ printk(KERN_ERR
     69  "bitmap out: size %d used %d off %d len %d align %d count %d\n",
     70  t->size, t->used, offset, len, align, count);
     71			return -1;
     72		}
     73
     74		if (offset + len > t->size) {
     75			count += t->size - offset;
     76			offset = 0;
     77			continue;
     78		}
     79
     80		i = 0;
     81		while (test_bit(offset + i, t->map) == 0) {
     82			i++;
     83			if (i == len) {
     84				bitmap_set(t->map, offset, len);
     85				if (offset == t->first_free)
     86					t->first_free = find_next_zero_bit
     87							(t->map, t->size,
     88							 t->first_free + len);
     89				if ((t->last_off = offset + len) >= t->size)
     90					t->last_off = 0;
     91				t->used += len;
     92				t->last_size = len;
     93				spin_unlock(&t->lock);
     94				return offset;
     95			}
     96		}
     97		count += i + 1;
     98		if ((offset += i + 1) >= t->size)
     99			offset = 0;
    100	}
    101}
    102
    103void bit_map_clear(struct bit_map *t, int offset, int len)
    104{
    105	int i;
    106
    107	if (t->used < len)
    108		BUG();		/* Much too late to do any good, but alas... */
    109	spin_lock(&t->lock);
    110	for (i = 0; i < len; i++) {
    111		if (test_bit(offset + i, t->map) == 0)
    112			BUG();
    113		__clear_bit(offset + i, t->map);
    114	}
    115	if (offset < t->first_free)
    116		t->first_free = offset;
    117	t->used -= len;
    118	spin_unlock(&t->lock);
    119}
    120
    121void bit_map_init(struct bit_map *t, unsigned long *map, int size)
    122{
    123	bitmap_zero(map, size);
    124	memset(t, 0, sizeof *t);
    125	spin_lock_init(&t->lock);
    126	t->map = map;
    127	t->size = size;
    128}