drm/omapdrm/tcm-sita.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
0004  *
0005  * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
0006  *          Lajos Molnar <molnar@ti.com>
0007  *          Andy Gross <andy.gross@ti.com>
0008  *
0009  * Copyright (C) 2012 Texas Instruments Incorporated - https://www.ti.com/
0010  */
0011 #include <linux/init.h>
0012 #include <linux/module.h>
0013 #include <linux/errno.h>
0014 #include <linux/sched.h>
0015 #include <linux/wait.h>
0016 #include <linux/bitmap.h>
0017 #include <linux/slab.h>
0018 #include "tcm.h"
0019
0020 static unsigned long mask[8];
0021 /*
0022  * pos      position in bitmap
0023  * w        width in slots
0024  * h        height in slots
0025  * map      ptr to bitmap
0026  * stride       slots in a row
0027  */
0028 static void free_slots(unsigned long pos, u16 w, u16 h,
0029         unsigned long *map, u16 stride)
0030 {
0031     int i;
0032
0033     for (i = 0; i < h; i++, pos += stride)
0034         bitmap_clear(map, pos, w);
0035 }
0036
0037 /*
0038  * w        width in slots
0039  * pos      ptr to position
0040  * map      ptr to bitmap
0041  * num_bits number of bits in bitmap
0042  */
0043 static int r2l_b2t_1d(u16 w, unsigned long *pos, unsigned long *map,
0044         size_t num_bits)
0045 {
0046     unsigned long search_count = 0;
0047     unsigned long bit;
0048     bool area_found = false;
0049
0050     *pos = num_bits - w;
0051
0052     while (search_count < num_bits) {
0053         bit = find_next_bit(map, num_bits, *pos);
0054
0055         if (bit - *pos >= w) {
0056             /* found a long enough free area */
0057             bitmap_set(map, *pos, w);
0058             area_found = true;
0059             break;
0060         }
0061
0062         search_count = num_bits - bit + w;
0063         *pos = bit - w;
0064     }
0065
0066     return (area_found) ? 0 : -ENOMEM;
0067 }
0068
0069 /*
0070  * w = width in slots
0071  * h = height in slots
0072  * a = align in slots   (mask, 2^n-1, 0 is unaligned)
0073  * offset = offset in bytes from 4KiB
0074  * pos = position in bitmap for buffer
0075  * map = bitmap ptr
0076  * num_bits = size of bitmap
0077  * stride = bits in one row of container
0078  */
0079 static int l2r_t2b(u16 w, u16 h, u16 a, s16 offset,
0080         unsigned long *pos, unsigned long slot_bytes,
0081         unsigned long *map, size_t num_bits, size_t slot_stride)
0082 {
0083     int i;
0084     unsigned long index;
0085     bool area_free = false;
0086     unsigned long slots_per_band = PAGE_SIZE / slot_bytes;
0087     unsigned long bit_offset = (offset > 0) ? offset / slot_bytes : 0;
0088     unsigned long curr_bit = bit_offset;
0089
0090     /* reset alignment to 1 if we are matching a specific offset */
0091     /* adjust alignment - 1 to get to the format expected in bitmaps */
0092     a = (offset > 0) ? 0 : a - 1;
0093
0094     /* FIXME Return error if slots_per_band > stride */
0095
0096     while (curr_bit < num_bits) {
0097         *pos = bitmap_find_next_zero_area(map, num_bits, curr_bit, w,
0098                 a);
0099
0100         /* skip forward if we are not at right offset */
0101         if (bit_offset > 0 && (*pos % slots_per_band != bit_offset)) {
0102             curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
0103             continue;
0104         }
0105
0106         /* skip forward to next row if we overlap end of row */
0107         if ((*pos % slot_stride) + w > slot_stride) {
0108             curr_bit = ALIGN(*pos, slot_stride) + bit_offset;
0109             continue;
0110         }
0111
0112         /* TODO: Handle overlapping 4K boundaries */
0113
0114         /* break out of look if we will go past end of container */
0115         if ((*pos + slot_stride * h) > num_bits)
0116             break;
0117
0118         /* generate mask that represents out matching pattern */
0119         bitmap_clear(mask, 0, slot_stride);
0120         bitmap_set(mask, (*pos % BITS_PER_LONG), w);
0121
0122         /* assume the area is free until we find an overlap */
0123         area_free = true;
0124
0125         /* check subsequent rows to see if complete area is free */
0126         for (i = 1; i < h; i++) {
0127             index = *pos / BITS_PER_LONG + i * 8;
0128             if (bitmap_intersects(&map[index], mask,
0129                 (*pos % BITS_PER_LONG) + w)) {
0130                 area_free = false;
0131                 break;
0132             }
0133         }
0134
0135         if (area_free)
0136             break;
0137
0138         /* go forward past this match */
0139         if (bit_offset > 0)
0140             curr_bit = ALIGN(*pos, slots_per_band) + bit_offset;
0141         else
0142             curr_bit = *pos + a + 1;
0143     }
0144
0145     if (area_free) {
0146         /* set area as in-use. iterate over rows */
0147         for (i = 0, index = *pos; i < h; i++, index += slot_stride)
0148             bitmap_set(map, index, w);
0149     }
0150
0151     return (area_free) ? 0 : -ENOMEM;
0152 }
0153
0154 static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
0155                struct tcm_area *area)
0156 {
0157     unsigned long pos;
0158     int ret;
0159
0160     spin_lock(&(tcm->lock));
0161     ret = r2l_b2t_1d(num_slots, &pos, tcm->bitmap, tcm->map_size);
0162     if (!ret) {
0163         area->p0.x = pos % tcm->width;
0164         area->p0.y = pos / tcm->width;
0165         area->p1.x = (pos + num_slots - 1) % tcm->width;
0166         area->p1.y = (pos + num_slots - 1) / tcm->width;
0167     }
0168     spin_unlock(&(tcm->lock));
0169
0170     return ret;
0171 }
0172
0173 static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u16 align,
0174                 s16 offset, u16 slot_bytes,
0175                 struct tcm_area *area)
0176 {
0177     unsigned long pos;
0178     int ret;
0179
0180     spin_lock(&(tcm->lock));
0181     ret = l2r_t2b(w, h, align, offset, &pos, slot_bytes, tcm->bitmap,
0182             tcm->map_size, tcm->width);
0183
0184     if (!ret) {
0185         area->p0.x = pos % tcm->width;
0186         area->p0.y = pos / tcm->width;
0187         area->p1.x = area->p0.x + w - 1;
0188         area->p1.y = area->p0.y + h - 1;
0189     }
0190     spin_unlock(&(tcm->lock));
0191
0192     return ret;
0193 }
0194
0195 static void sita_deinit(struct tcm *tcm)
0196 {
0197     kfree(tcm);
0198 }
0199
0200 static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
0201 {
0202     unsigned long pos;
0203     u16 w, h;
0204
0205     pos = area->p0.x + area->p0.y * tcm->width;
0206     if (area->is2d) {
0207         w = area->p1.x - area->p0.x + 1;
0208         h = area->p1.y - area->p0.y + 1;
0209     } else {
0210         w = area->p1.x + area->p1.y * tcm->width - pos + 1;
0211         h = 1;
0212     }
0213
0214     spin_lock(&(tcm->lock));
0215     free_slots(pos, w, h, tcm->bitmap, tcm->width);
0216     spin_unlock(&(tcm->lock));
0217     return 0;
0218 }
0219
0220 struct tcm *sita_init(u16 width, u16 height)
0221 {
0222     struct tcm *tcm;
0223     size_t map_size = BITS_TO_LONGS(width*height) * sizeof(unsigned long);
0224
0225     if (width == 0 || height == 0)
0226         return NULL;
0227
0228     tcm = kzalloc(sizeof(*tcm) + map_size, GFP_KERNEL);
0229     if (!tcm)
0230         goto error;
0231
0232     /* Updating the pointers to SiTA implementation APIs */
0233     tcm->height = height;
0234     tcm->width = width;
0235     tcm->reserve_2d = sita_reserve_2d;
0236     tcm->reserve_1d = sita_reserve_1d;
0237     tcm->free = sita_free;
0238     tcm->deinit = sita_deinit;
0239
0240     spin_lock_init(&tcm->lock);
0241     tcm->bitmap = (unsigned long *)(tcm + 1);
0242     bitmap_clear(tcm->bitmap, 0, width*height);
0243
0244     tcm->map_size = width*height;
0245
0246     return tcm;
0247
0248 error:
0249     return NULL;
0250 }