summaryrefslogtreecommitdiff
blob: dae2517801ee1c1e6ee3ea896df5c947c299c4c7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
#! /bin/bash
#
# Copyright 2021 Gentoo Authors
# Distributed under the terms of the GNU General Public License v2
#
# Author:  Jaco Kroon <jaco@uls.co.za>
# So that you can contact me if you need help with the below insanity.
#
# Configuration options:
# selection_ranges => an array of start-stop values.  There is an assumption of
#  incremental ordering, ie, start values should be in incrementing order, and
# debug => if non-zero outputs some cryptic debug output (will inherit from environment).
#
selection_ranges=(
	499-101
	500-749
	#60001-60999
)
debug=${debug:+1} # set non-zero to enable debug output.

#
# Basic Design:
#
# There is nothing beautiful about this script, it's downright nasty and I
# (Jaco Kroon <jaco@uls.co.za>) will be the first to admit that.
#
# For each of the uid and gid ranges, we primarily keep two variables.
# ranges and reason.  reason is simply one of USED or RESERVED.  Free ranges
# are not mapped into these arrays.
# ranges_ maps a start index onto an end index.  So for example, let's say
# uid range 0..10 is USED (allocated, for whatever purposes):
#
# ranges_uid[0]=10
# reasons_uid[0]=USED
#
# The above says that UID 0 to 10 is USED.
#
# We start with an initially empty set, and then insert into, either merging or
# potentially splitting as we go, by way of the consume function, once completed
# we compact some things and then output.
#

ranges_uid=()
ranges_gid=()
reason_uid=()
reason_gid=()

# Colours to be used if output is a TTY.
colour_USED="\e[0;91m" # brightred
colour_FREE="\e[0;92m" # brightgreen
colour_RESERVED="\e[0;94m" # brightblue
colour_RESET="\e[0m" # reset all styles.

if ! [[ -t 1 ]]; then
	colour_USED=
	colour_FREE=
	colour_RESERVED=
	colour_RESET=
fi

# Find input file if not piped in on stdin, or show a warning about it on
# stderr if we can't find the file.
if [[ -t 0 ]]; then
	def_infile="$(dirname "$0")/../files/uid-gid.txt"
	if ! [[ -r "${def_infile}" ]] || ! exec <"${def_infile}"; then
		echo "Reading from stdin (which happens to be a tty, you should pipe input file to stdin)" >&2
	fi
fi

consume()
{
	# The basic principle here is that we can either add a new range, or split
	# an existing range.  Partial overlaps not dealt with, nor range
	# extensions.  Which would (I believe) negate the need for compact.
	# TODO:  deal with range merging here, eg, if we have 0..10, and adding 11, then
	# we can simply adjust the range to 0..11, for example.
	local variant="$1"
	local ids="$2"
	local type=$([[ "$3" == reserved ]] && echo RESERVED || echo USED)
	local range_start="${ids%..*}"
	local range_end="${ids#*..}"
	declare -n ranges="ranges_${variant}"
	declare -n reasons="reason_${variant}"

	[[ -z "${ids}" ]] && return
	[[ "${ids}" == - ]] && return

	for k in "${!ranges[@]}"; do
		# can the new range be inserted before the next range already in the set?
		[[ ${k} -gt ${range_end} ]] && break
		[[ ${ranges[k]} -lt ${range_start} ]] && continue
		if [[ ${k} -le ${range_start} && ${range_end} -le ${ranges[k]} ]]; then
			# new range is contained completely inside.
			[[ ${reasons[k]} == ${type} ]] && return # same type.
			[[ ${type} == RESERVED ]] && return # USED takes precedence over RESERVED.

			if [[ ${range_end} -lt ${ranges[k]} ]]; then
				ranges[range_end+1]=${ranges[k]}
				reasons[range_end+1]=${reasons[k]}
			fi
			[[ ${range_start} -gt ${k} ]] && ranges[k]=$(( range_start - 1 ))
			break
		else
			echo "${range_start}..${range_end} (${type}) overlaps with ${k}..${ranges[k]} (${reasons[k]}"
			echo "Cannot handle partial overlap."
			exit 1
		fi
	done

	ranges[range_start]="${range_end}"
	reasons[range_start]="${type}"
}

compact()
{
	# This simply coalesces ranges that follow directly on each other.  In
	# other words, if range ends at 10 and the next range starts at 11, just
	# merge the two by adjusting the end of the first range, and removing the
	# immediately following.
	# Param: uid or gid to determine which set we're working with.
	declare -n ranges="ranges_$1"
	declare -n reasons="reason_$1"
	local k e ne
	for k in "${ranges[@]}"; do
		[[ -n "${ranges[k]:+set}" ]] || continue
		e=${ranges[k]}
		while [[ -n "${ranges[e+1]:+set}" && "${reasons[k]}" == "${reasons[e+1]}" ]]; do
			ne=${ranges[e+1]}
			unset "ranges[e+1]"
			e=${ne}
		done
		ranges[k]=${e}
	done
}

output()
{
	# Outputs the raw list as provided (param:  uid or gid)
	declare -n ranges="ranges_$1"
	declare -n reasons="reason_$1"
	local k c=0

	echo "$1 list:"
	for k in "${!ranges[@]}"; do
		echo "$(( c++ )): ${k} => ${ranges[k]} / ${reasons[k]}"
	done
}

# Read the input file which is structured as "username uid gid provider and
# potentially more stuff" Lines starting with # are comments, thus we can
# filter those out.
while read un uid gid provider rest; do
	[[ "${un}" == \#* ]] && continue
	consume uid "${uid}" "${provider}"
	consume gid "${gid}" "${provider}"
done

compact uid
compact gid

# If we're debugging, just output both lists so we can inspect that everything is correct here.
if [[ -n "${debug}" ]]; then
	output uid
	output gid
fi

# Get the various range starts.
uids=("${!ranges_uid[@]}")
gids=("${!ranges_gid[@]}")

# Set max to 2^32-1 if set to -.
if [[ ${max} == - ]]; then
	max=$((2 ** 32 - 1))
fi

ui=0 # index into uids array.
gi=0 # index into gids array.

free_total_uid=0
free_total_gid=0
free_total_pair=0

for r in "${selection_ranges[@]}"; do
	min=${r%-*} # "start" of range about to be output.
	max=${r#*-} # "end" of range about to be output.
	selection=min
	if [[ $max -lt $min ]]; then
		selection=max
		t=${max}
		max=${min}
		min=${t}
	fi

	freeuid=0 # count number of free UIDs
	freegid=0 # count number of free GIDs
	freepair=0 # count number of free UID+GID pairs.

	echo "Range: ${min}..${max} (${selection})"
	printf "%-*s%10s%10s\n" $(( ${#max} * 2 + 5 )) "#ID" UID GID

	idbase=${min}
	while [[ ${idbase} -le ${max} ]]; do
		# skip over uid and gid ranges that we're no longer interested in (end of range is
		# lower than start of output range).
		while [[ ${ui} -lt ${#uids[@]} && ${ranges_uid[uids[ui]]} -lt ${idbase} ]]; do
			(( ui++ ))
		done
		while [[ ${gi} -lt ${#gids[@]} && ${ranges_gid[gids[gi]]} -lt ${idbase} ]]; do
			(( gi++ ))
		done
		# Assume that range we're going to output is the remainder of the legal
		# space we're interested in, and then adjust downwards as needed.  For each
		# of the UID and GID space, if the start range is beyond the current output
		# start we're looking at a FREE range, so downward adjust re (range end) to
		# the next non-FREE range's start - 1, or if we're in the non-FREE range,
		# adjust downward to that range's end.
		re=${max}
		uid_start=-1
		gid_start=-1
		if [[ ${ui} -lt ${#uids[@]} ]]; then
			uid_start=${uids[ui]}
			if [[ ${uid_start} -gt ${idbase} && ${uid_start} -le ${re} ]]; then
				re=$(( ${uid_start} - 1 ))
			fi
			if [[ ${ranges_uid[uid_start]} -lt ${re} ]]; then
				re=${ranges_uid[uid_start]}
			fi
		fi
		if [[ ${gi} -lt ${#gids[@]} ]]; then
			gid_start=${gids[gi]}
			if [[ ${gid_start} -gt ${idbase} && ${gid_start} -le ${re} ]]; then
				re=$(( ${gid_start} - 1 ))
			fi
			if [[ ${ranges_gid[gid_start]} -lt ${re} ]]; then
				re=${ranges_gid[gid_start]}
			fi
		fi

		# If we're debugging, just dump various variables above, which allows
		# validating that the above logic works correctly.
		[[ -n "${debug}" ]] && echo "ui=${ui} (${uid_start}..${ranges_uid[uid_start]}), gi=${gi} (${gid_start}..${ranges_gid[gid_start]}), idbase=${idbase}, re=${re}"

		# Determine the state of the UID and GID ranges.
		if [[ ${ui} -lt ${#uids[@]} && ${uid_start} -le ${idbase} ]]; then
			uidstate="${reason_uid[uid_start]}"
		else
			uidstate=FREE
			freeuid=$(( freeuid + re - idbase + 1 ))
		fi

		if [[ ${gi} -lt ${#gids[@]} && ${gid_start} -le ${idbase} ]]; then
			gidstate="${reason_gid[gids[gi]]}"
		else
			gidstate=FREE
			freegid=$(( freegid + re - idbase + 1 ))
		fi

		# If the ranges are FREE (or at least one of), adjust selection recommendations
		# accordingly.
		if [[ "${gidstate}" == FREE ]]; then
			if [[ "${uidstate}" == FREE ]]; then
				case "${selection}" in
					min)
						[[ -z "${uidgidboth}" ]] && uidgidboth=${idbase}
						;;
					max)
						[[ -z "${uidgidboth}" || ${uidgidboth} -ge ${min} ]] && uidgidboth=${re}
						;;
				esac
				freepair=$(( freepair + re - idbase + 1 ))
			else
				case "${selection}" in
					min)
						[[ -z "${gidonly}" ]] && gidonly=${idbase}
						;;
					max)
						[[ -z "${gidonly}" || ${gidonly} -ge ${min} ]] && gidonly=${re}
						;;
				esac
			fi
		elif [[ "${uidstate}" == FREE ]]; then
			case "${selection}" in
				min)
					[[ -z "${uidonly}" ]] && uidonly=${idbase}
					;;
				max)
					[[ -z "${uidonly}" || ${uidonly} -ge ${min} ]] && uidonly=${re}
					;;
			esac
		fi

		vn="colour_${uidstate}"
		colour_uid="${!vn}"
		vn="colour_${gidstate}"
		colour_gid="${!vn}"
		printf "%-*s${colour_uid}%10s${colour_gid}%10s${colour_RESET}\n" $(( ${#max} * 2 + 5 )) "${idbase}$([[ ${re} -gt ${idbase} ]] && echo "..${re}")" "${uidstate}" "${gidstate}"
		idbase=$(( re + 1 ))
	done
	echo "Range Free UIDs: ${freeuid}"
	echo "Range Free GIDs: ${freegid}"
	echo "Range Free UID+GID pairs: ${freepair}"
	echo
	(( free_total_uid += freeuid ))
	(( free_total_gid += freegid ))
	(( free_total_pair += freepair ))
done

echo "Free UIDs: ${free_total_uid}"
echo "Free GIDs: ${free_total_gid}"
echo "Free UID+GID pairs: ${free_total_pair}"
echo

for out in "Recommended GID only: ${gidonly:-${uidgidboth:-none}}" \
	   "Recommended UID only: ${uidonly:-${uidgidboth:-none}}" \
	   "Recommended UID+GID pair: ${uidgidboth:-none}"; do
    [[ ${out} == *none ]] && colour=${colour_USED} || colour=${colour_FREE}
    echo -e "${out%%: *}: ${colour}${out#*: }${colour_RESET}"
done