^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Range add and subtract
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) #include <linux/init.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/minmax.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/printk.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #include <linux/sort.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include <linux/string.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include <linux/range.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) int add_range(struct range *range, int az, int nr_range, u64 start, u64 end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) if (start >= end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) return nr_range;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) /* Out of slots: */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) if (nr_range >= az)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) return nr_range;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) range[nr_range].start = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) range[nr_range].end = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) nr_range++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) return nr_range;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) int add_range_with_merge(struct range *range, int az, int nr_range,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) u64 start, u64 end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) if (start >= end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) return nr_range;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) /* get new start/end: */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) for (i = 0; i < nr_range; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) u64 common_start, common_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) if (!range[i].end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) common_start = max(range[i].start, start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) common_end = min(range[i].end, end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) if (common_start > common_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) /* new start/end, will add it back at last */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) start = min(range[i].start, start);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) end = max(range[i].end, end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) memmove(&range[i], &range[i + 1],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) (nr_range - (i + 1)) * sizeof(range[i]));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) range[nr_range - 1].start = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) range[nr_range - 1].end = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) nr_range--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) i--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) /* Need to add it: */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) return add_range(range, az, nr_range, start, end);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) void subtract_range(struct range *range, int az, u64 start, u64 end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) int i, j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) if (start >= end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) for (j = 0; j < az; j++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) if (!range[j].end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) if (start <= range[j].start && end >= range[j].end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) range[j].start = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) range[j].end = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) if (start <= range[j].start && end < range[j].end &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) range[j].start < end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) range[j].start = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) if (start > range[j].start && end >= range[j].end &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) range[j].end > start) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) range[j].end = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) if (start > range[j].start && end < range[j].end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) /* Find the new spare: */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) for (i = 0; i < az; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) if (range[i].end == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) if (i < az) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) range[i].end = range[j].end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) range[i].start = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) pr_err("%s: run out of slot in ranges\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) __func__);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) range[j].end = start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) static int cmp_range(const void *x1, const void *x2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) const struct range *r1 = x1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) const struct range *r2 = x2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) if (r1->start < r2->start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) if (r1->start > r2->start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) int clean_sort_range(struct range *range, int az)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) int i, j, k = az - 1, nr_range = az;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) for (i = 0; i < k; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) if (range[i].end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) for (j = k; j > i; j--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) if (range[j].end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) k = j;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) if (j == i)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) range[i].start = range[k].start;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) range[i].end = range[k].end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) range[k].start = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) range[k].end = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) k--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) /* count it */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) for (i = 0; i < az; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) if (!range[i].end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) nr_range = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) /* sort them */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) return nr_range;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) void sort_range(struct range *range, int nr_range)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) /* sort them */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) sort(range, nr_range, sizeof(struct range), cmp_range, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags