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

tcm-sita.c (5919B)


      1// SPDX-License-Identifier: GPL-2.0-only
      2/*
      3 * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
      4 *
      5 * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
      6 *          Lajos Molnar <molnar@ti.com>
      7 *          Andy Gross <andy.gross@ti.com>
      8 *
      9 * Copyright (C) 2012 Texas Instruments Incorporated - https://www.ti.com/
     10 */
     11#include <linux/init.h>
     12#include <linux/module.h>
     13#include <linux/errno.h>
     14#include <linux/sched.h>
     15#include <linux/wait.h>
     16#include <linux/bitmap.h>
     17#include <linux/slab.h>
     18#include "tcm.h"
     19
     20static unsigned long mask[8];
     21/*
     22 * pos		position in bitmap
     23 * w		width in slots
     24 * h		height in slots
     25 * map		ptr to bitmap
     26 * stride		slots in a row
     27 */
     28static void free_slots(unsigned long pos, u16 w, u16 h,
     29		unsigned long *map, u16 stride)
     30{
     31	int i;
     32
     33	for (i = 0; i < h; i++, pos += stride)
     34		bitmap_clear(map, pos, w);
     35}
     36
     37/*
     38 * w		width in slots
     39 * pos		ptr to position
     40 * map		ptr to bitmap
     41 * num_bits	number of bits in bitmap
     42 */
     43static int r2l_b2t_1d(u16 w, unsigned long *pos, unsigned long *map,
     44		size_t num_bits)
     45{
     46	unsigned long search_count = 0;
     47	unsigned long bit;
     48	bool area_found = false;
     49
     50	*pos = num_bits - w;
     51
     52	while (search_count < num_bits) {
     53		bit = find_next_bit(map, num_bits, *pos);
     54
     55		if (bit - *pos >= w) {
     56			/* found a long enough free area */
     57			bitmap_set(map, *pos, w);
     58			area_found = true;
     59			break;
     60		}
     61
     62		search_count = num_bits - bit + w;
     63		*pos = bit - w;
     64	}
     65
     66	return (area_found) ? 0 : -ENOMEM;
     67}
     68
     69/*
     70 * w = width in slots
     71 * h = height in slots
     72 * a = align in slots	(mask, 2^n-1, 0 is unaligned)
     73 * offset = offset in bytes from 4KiB
     74 * pos = position in bitmap for buffer
     75 * map = bitmap ptr
     76 * num_bits = size of bitmap
     77 * stride = bits in one row of container
     78 */
     79static int l2r_t2b(u16 w, u16 h, u16 a, s16 offset,
     80		unsigned long *pos, unsigned long slot_bytes,
     81		unsigned long *map, size_t num_bits, size_t slot_stride)
     82{
     83	int i;
     84	unsigned long index;
     85	bool area_free = false;
     86	unsigned long slots_per_band = PAGE_SIZE / slot_bytes;
     87	unsigned long bit_offset = (offset > 0) ? offset / slot_bytes : 0;
     88	unsigned long curr_bit = bit_offset;
     89
     90	/* reset alignment to 1 if we are matching a specific offset */
     91	/* adjust alignment - 1 to get to the format expected in bitmaps */
     92	a = (offset > 0) ? 0 : a - 1;
     93
     94	/* FIXME Return error if slots_per_band > stride */
     95
     96	while (curr_bit < num_bits) {
     97		*pos = bitmap_find_next_zero_area(map, num_bits, curr_bit, w,
     98				a);
     99
    100		/* skip forward if we are not at right offset */
    101		if (bit_offset > 0 && (*pos % slots_per_band != bit_offset)) {
    102			curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
    103			continue;
    104		}
    105
    106		/* skip forward to next row if we overlap end of row */
    107		if ((*pos % slot_stride) + w > slot_stride) {
    108			curr_bit = ALIGN(*pos, slot_stride) + bit_offset;
    109			continue;
    110		}
    111
    112		/* TODO: Handle overlapping 4K boundaries */
    113
    114		/* break out of look if we will go past end of container */
    115		if ((*pos + slot_stride * h) > num_bits)
    116			break;
    117
    118		/* generate mask that represents out matching pattern */
    119		bitmap_clear(mask, 0, slot_stride);
    120		bitmap_set(mask, (*pos % BITS_PER_LONG), w);
    121
    122		/* assume the area is free until we find an overlap */
    123		area_free = true;
    124
    125		/* check subsequent rows to see if complete area is free */
    126		for (i = 1; i < h; i++) {
    127			index = *pos / BITS_PER_LONG + i * 8;
    128			if (bitmap_intersects(&map[index], mask,
    129				(*pos % BITS_PER_LONG) + w)) {
    130				area_free = false;
    131				break;
    132			}
    133		}
    134
    135		if (area_free)
    136			break;
    137
    138		/* go forward past this match */
    139		if (bit_offset > 0)
    140			curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
    141		else
    142			curr_bit = *pos + a + 1;
    143	}
    144
    145	if (area_free) {
    146		/* set area as in-use. iterate over rows */
    147		for (i = 0, index = *pos; i < h; i++, index += slot_stride)
    148			bitmap_set(map, index, w);
    149	}
    150
    151	return (area_free) ? 0 : -ENOMEM;
    152}
    153
    154static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
    155			   struct tcm_area *area)
    156{
    157	unsigned long pos;
    158	int ret;
    159
    160	spin_lock(&(tcm->lock));
    161	ret = r2l_b2t_1d(num_slots, &pos, tcm->bitmap, tcm->map_size);
    162	if (!ret) {
    163		area->p0.x = pos % tcm->width;
    164		area->p0.y = pos / tcm->width;
    165		area->p1.x = (pos + num_slots - 1) % tcm->width;
    166		area->p1.y = (pos + num_slots - 1) / tcm->width;
    167	}
    168	spin_unlock(&(tcm->lock));
    169
    170	return ret;
    171}
    172
    173static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u16 align,
    174				s16 offset, u16 slot_bytes,
    175				struct tcm_area *area)
    176{
    177	unsigned long pos;
    178	int ret;
    179
    180	spin_lock(&(tcm->lock));
    181	ret = l2r_t2b(w, h, align, offset, &pos, slot_bytes, tcm->bitmap,
    182			tcm->map_size, tcm->width);
    183
    184	if (!ret) {
    185		area->p0.x = pos % tcm->width;
    186		area->p0.y = pos / tcm->width;
    187		area->p1.x = area->p0.x + w - 1;
    188		area->p1.y = area->p0.y + h - 1;
    189	}
    190	spin_unlock(&(tcm->lock));
    191
    192	return ret;
    193}
    194
    195static void sita_deinit(struct tcm *tcm)
    196{
    197	kfree(tcm);
    198}
    199
    200static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
    201{
    202	unsigned long pos;
    203	u16 w, h;
    204
    205	pos = area->p0.x + area->p0.y * tcm->width;
    206	if (area->is2d) {
    207		w = area->p1.x - area->p0.x + 1;
    208		h = area->p1.y - area->p0.y + 1;
    209	} else {
    210		w = area->p1.x + area->p1.y * tcm->width - pos + 1;
    211		h = 1;
    212	}
    213
    214	spin_lock(&(tcm->lock));
    215	free_slots(pos, w, h, tcm->bitmap, tcm->width);
    216	spin_unlock(&(tcm->lock));
    217	return 0;
    218}
    219
    220struct tcm *sita_init(u16 width, u16 height)
    221{
    222	struct tcm *tcm;
    223	size_t map_size = BITS_TO_LONGS(width*height) * sizeof(unsigned long);
    224
    225	if (width == 0 || height == 0)
    226		return NULL;
    227
    228	tcm = kzalloc(sizeof(*tcm) + map_size, GFP_KERNEL);
    229	if (!tcm)
    230		goto error;
    231
    232	/* Updating the pointers to SiTA implementation APIs */
    233	tcm->height = height;
    234	tcm->width = width;
    235	tcm->reserve_2d = sita_reserve_2d;
    236	tcm->reserve_1d = sita_reserve_1d;
    237	tcm->free = sita_free;
    238	tcm->deinit = sita_deinit;
    239
    240	spin_lock_init(&tcm->lock);
    241	tcm->bitmap = (unsigned long *)(tcm + 1);
    242	bitmap_clear(tcm->bitmap, 0, width*height);
    243
    244	tcm->map_size = width*height;
    245
    246	return tcm;
    247
    248error:
    249	return NULL;
    250}