Implement serial validation for selection requests

This change tracks, for each wlr_seat_client, the most recent serial
numbers which were sent to the client. When the client makes a
selection request, wlroots now verifies that the serial number
associated with the selection request was actually provided to that
specific client. This ensures that the client that was most
recently interacted with always has priority for its copy selection
requests, and that no other clients can incorrectly use a larger serial
value and "steal" the role of having the copy selection.

Also, the code used to determine when a given selection is superseded
by a newer request uses < instead of <= to allow clients to make
multiple selection requests with the same serial number and have the
last one hold.

To limit memory use, a ring buffer is used to store runs of sequential
serial numbers, and all serial numbers earlier than the start of the
ring buffer are assumed to be valid. Faking very old serials is
unlikely to be disruptive.

Assuming all clients are correctly written, the only additional
constraint which this patch should impose is that serial numbers
are now bound to seats: clients may not receive a serial number
from an input event on one seat and then use that to request
copy-selection on another seat.

13 files changed, 124 insertions, 26 deletions

diff --git a/include/wlr/types/wlr_data_device.h b/include/wlr/types/wlr_data_device.h
index 256654e5..d8894d6e 100644
--- a/include/wlr/types/wlr_data_device.h
+++ b/include/wlr/types/wlr_data_device.h
@@ -168,10 +168,14 @@ struct wlr_data_device_manager *wlr_data_device_manager_create(
 void wlr_data_device_manager_destroy(struct wlr_data_device_manager *manager);
 
 /**
- * Requests a selection to be set for the seat.
+ * Requests a selection to be set for the seat. If the request comes from
+ * a client, then set `client` to be the matching seat client so that this
+ * function can verify that the serial provided was once sent to the client
+ * on this seat.
  */
 void wlr_seat_request_set_selection(struct wlr_seat *seat,
-	struct wlr_data_source *source, uint32_t serial);
+	struct wlr_seat_client *client, struct wlr_data_source *source,
+	uint32_t serial);
 
 /**
  * Sets the current selection for the seat. NULL can be provided to clear it.
diff --git a/include/wlr/types/wlr_primary_selection.h b/include/wlr/types/wlr_primary_selection.h
index b1d45b61..4df47380 100644
--- a/include/wlr/types/wlr_primary_selection.h
+++ b/include/wlr/types/wlr_primary_selection.h
@@ -48,7 +48,13 @@ void wlr_primary_selection_source_send(
 	struct wlr_primary_selection_source *source, const char *mime_type,
 	int fd);
 
+/**
+ * Request setting the primary selection. If `client` is not null, then the
+ * serial will be checked against the set of serials sent to the client on that
+ * seat.
+ */
 void wlr_seat_request_set_primary_selection(struct wlr_seat *seat,
+	struct wlr_seat_client *client,
 	struct wlr_primary_selection_source *source, uint32_t serial);
 /**
  * Sets the current primary selection for the seat. NULL can be provided to
diff --git a/include/wlr/types/wlr_seat.h b/include/wlr/types/wlr_seat.h
index bfd3625d..f19d4e35 100644
--- a/include/wlr/types/wlr_seat.h
+++ b/include/wlr/types/wlr_seat.h
@@ -15,6 +15,31 @@
 #include <wlr/types/wlr_keyboard.h>
 #include <wlr/types/wlr_surface.h>
 
+#define WLR_SERIAL_RINGSET_SIZE 128
+
+struct wlr_serial_range {
+	uint32_t min_incl;
+	uint32_t max_incl;
+};
+
+struct wlr_serial_ringset {
+	struct wlr_serial_range data[WLR_SERIAL_RINGSET_SIZE];
+	int end;
+	int count;
+};
+
+/**
+ * Add a new serial number to the set. The number must be larger than
+ * all other values already added
+ */
+void wlr_serial_add(struct wlr_serial_ringset *set, uint32_t serial);
+
+/**
+ * Return false if the serial number is definitely not in the set, true
+ * otherwise.
+ */
+bool wlr_serial_maybe_valid(struct wlr_serial_ringset *set, uint32_t serial);
+
 /**
  * Contains state for a single client's bound wl_seat resource and can be used
  * to issue input events to that client. The lifetime of these objects is
@@ -35,6 +60,9 @@ struct wlr_seat_client {
 	struct {
 		struct wl_signal destroy;
 	} events;
+
+	// set of serials which were sent to the client on this seat
+	struct wlr_serial_ringset serials;
 };
 
 struct wlr_touch_point {
@@ -622,6 +650,13 @@ bool wlr_seat_validate_touch_grab_serial(struct wlr_seat *seat,
 	struct wlr_touch_point **point_ptr);
 
 /**
+ * Return a new serial (from wl_display_serial_next()) for the client, and
+ * update the seat client's set of valid serials. Use this for all input
+ * events.
+ */
+uint32_t wlr_seat_client_next_serial(struct wlr_seat_client *client);
+
+/**
  * Get a seat client from a seat resource. Returns NULL if inert.
  */
 struct wlr_seat_client *wlr_seat_client_from_resource(
diff --git a/types/data_device/wlr_data_device.c b/types/data_device/wlr_data_device.c
index d494cf75..7ef3d342 100644
--- a/types/data_device/wlr_data_device.c
+++ b/types/data_device/wlr_data_device.c
@@ -41,7 +41,7 @@ static void data_device_set_selection(struct wl_client *client,
 
 	struct wlr_data_source *wlr_source =
 		source != NULL ? &source->source : NULL;
-	wlr_seat_request_set_selection(seat_client->seat, wlr_source, serial);
+	wlr_seat_request_set_selection(seat_client->seat, seat_client, wlr_source, serial);
 }
 
 static void data_device_start_drag(struct wl_client *client,
@@ -142,11 +142,18 @@ void seat_client_send_selection(struct wlr_seat_client *seat_client) {
 }
 
 void wlr_seat_request_set_selection(struct wlr_seat *seat,
+		struct wlr_seat_client *client,
 		struct wlr_data_source *source, uint32_t serial) {
+	if (client && !wlr_serial_maybe_valid(&client->serials, serial)) {
+		wlr_log(WLR_DEBUG, "Rejecting set_selection request, "
+			"serial %"PRIu32" was never given to client", serial);
+		return;
+	}
+
 	if (seat->selection_source &&
-			seat->selection_serial - serial < UINT32_MAX / 2) {
-		wlr_log(WLR_DEBUG, "Rejecting set_selection request, invalid serial "
-			"(%"PRIu32" <= %"PRIu32")", serial, seat->selection_serial);
+			serial - seat->selection_serial > UINT32_MAX / 2) {
+		wlr_log(WLR_DEBUG, "Rejecting set_selection request, serial indicates superseded "
+			"(%"PRIu32" < %"PRIu32")", serial, seat->selection_serial);
 		return;
 	}
 
diff --git a/types/seat/wlr_seat.c b/types/seat/wlr_seat.c
index 879a7513..c0ae90c6 100644
--- a/types/seat/wlr_seat.c
+++ b/types/seat/wlr_seat.c
@@ -370,3 +370,36 @@ bool wlr_seat_validate_grab_serial(struct wlr_seat *seat, uint32_t serial) {
 	//	serial == seat->touch_state.grab_serial;
 	return true;
 }
+
+void wlr_serial_add(struct wlr_serial_ringset *set, uint32_t serial) {
+	if (set->count == 0 || set->data[set->end].max_incl + 1 != serial) {
+		set->count++;
+		if (set->count > WLR_SERIAL_RINGSET_SIZE) {
+			set->count = WLR_SERIAL_RINGSET_SIZE;
+		}
+		set->end = (set->end + 1) % WLR_SERIAL_RINGSET_SIZE;
+		set->data[set->end].min_incl = serial;
+		set->data[set->end].max_incl = serial;
+	} else {
+		set->data[set->end].max_incl = serial;
+	}
+}
+
+bool wlr_serial_maybe_valid(struct wlr_serial_ringset *set, uint32_t serial) {
+	for (int i = 0; i < set->count; i++) {
+		int j = (set->end - i + WLR_SERIAL_RINGSET_SIZE) % WLR_SERIAL_RINGSET_SIZE;
+		if (set->data[j].max_incl - serial > UINT32_MAX / 2) {
+			return false;
+		}
+		if (serial - set->data[j].min_incl <= UINT32_MAX / 2) {
+			return true;
+		}
+	}
+	return true;
+}
+
+uint32_t wlr_seat_client_next_serial(struct wlr_seat_client *client) {
+	uint32_t serial = wl_display_next_serial(wl_client_get_display(client->client));
+	wlr_serial_add(&client->serials, serial);
+	return serial;
+}
diff --git a/types/seat/wlr_seat_keyboard.c b/types/seat/wlr_seat_keyboard.c
index c92103eb..fef3b502 100644
--- a/types/seat/wlr_seat_keyboard.c
+++ b/types/seat/wlr_seat_keyboard.c
@@ -72,7 +72,7 @@ void wlr_seat_keyboard_send_key(struct wlr_seat *wlr_seat, uint32_t time,
 		return;
 	}
 
-	uint32_t serial = wl_display_next_serial(wlr_seat->display);
+	uint32_t serial = wlr_seat_client_next_serial(client);
 	struct wl_resource *resource;
 	wl_resource_for_each(resource, &client->keyboards) {
 		if (seat_client_from_keyboard_resource(resource) == NULL) {
@@ -201,7 +201,7 @@ void wlr_seat_keyboard_send_modifiers(struct wlr_seat *seat,
 		return;
 	}
 
-	uint32_t serial = wl_display_next_serial(seat->display);
+	uint32_t serial = wlr_seat_client_next_serial(client);
 	struct wl_resource *resource;
 	wl_resource_for_each(resource, &client->keyboards) {
 		if (seat_client_from_keyboard_resource(resource) == NULL) {
@@ -240,7 +240,7 @@ void wlr_seat_keyboard_enter(struct wlr_seat *seat,
 
 	// leave the previously entered surface
 	if (focused_client != NULL && focused_surface != NULL) {
-		uint32_t serial = wl_display_next_serial(seat->display);
+		uint32_t serial = wlr_seat_client_next_serial(focused_client);
 		struct wl_resource *resource;
 		wl_resource_for_each(resource, &focused_client->keyboards) {
 			if (seat_client_from_keyboard_resource(resource) == NULL) {
@@ -263,7 +263,7 @@ void wlr_seat_keyboard_enter(struct wlr_seat *seat,
 			}
 			*p = keycodes[i];
 		}
-		uint32_t serial = wl_display_next_serial(seat->display);
+		uint32_t serial = wlr_seat_client_next_serial(client);
 		struct wl_resource *resource;
 		wl_resource_for_each(resource, &client->keyboards) {
 			if (seat_client_from_keyboard_resource(resource) == NULL) {
diff --git a/types/seat/wlr_seat_pointer.c b/types/seat/wlr_seat_pointer.c
index e2034c78..ac5ac88b 100644
--- a/types/seat/wlr_seat_pointer.c
+++ b/types/seat/wlr_seat_pointer.c
@@ -149,7 +149,7 @@ void wlr_seat_pointer_enter(struct wlr_seat *wlr_seat,
 
 	// leave the previously entered surface
 	if (focused_client != NULL && focused_surface != NULL) {
-		uint32_t serial = wl_display_next_serial(wlr_seat->display);
+		uint32_t serial = wlr_seat_client_next_serial(focused_client);
 		struct wl_resource *resource;
 		wl_resource_for_each(resource, &focused_client->pointers) {
 			if (wlr_seat_client_from_pointer_resource(resource) == NULL) {
@@ -163,7 +163,7 @@ void wlr_seat_pointer_enter(struct wlr_seat *wlr_seat,
 
 	// enter the current surface
 	if (client != NULL && surface != NULL) {
-		uint32_t serial = wl_display_next_serial(wlr_seat->display);
+		uint32_t serial = wlr_seat_client_next_serial(client);
 		struct wl_resource *resource;
 		wl_resource_for_each(resource, &client->pointers) {
 			if (wlr_seat_client_from_pointer_resource(resource) == NULL) {
@@ -242,7 +242,7 @@ uint32_t wlr_seat_pointer_send_button(struct wlr_seat *wlr_seat, uint32_t time,
 		return 0;
 	}
 
-	uint32_t serial = wl_display_next_serial(wlr_seat->display);
+	uint32_t serial = wlr_seat_client_next_serial(client);
 	struct wl_resource *resource;
 	wl_resource_for_each(resource, &client->pointers) {
 		if (wlr_seat_client_from_pointer_resource(resource) == NULL) {
diff --git a/types/seat/wlr_seat_touch.c b/types/seat/wlr_seat_touch.c
index 75b304a5..1d454225 100644
--- a/types/seat/wlr_seat_touch.c
+++ b/types/seat/wlr_seat_touch.c
@@ -278,7 +278,7 @@ uint32_t wlr_seat_touch_send_down(struct wlr_seat *seat,
 		return 0;
 	}
 
-	uint32_t serial = wl_display_next_serial(seat->display);
+	uint32_t serial = wlr_seat_client_next_serial(point->client);
 	struct wl_resource *resource;
 	wl_resource_for_each(resource, &point->client->touches) {
 		if (seat_client_from_touch_resource(resource) == NULL) {
@@ -299,7 +299,7 @@ void wlr_seat_touch_send_up(struct wlr_seat *seat, uint32_t time, int32_t touch_
 		return;
 	}
 
-	uint32_t serial = wl_display_next_serial(seat->display);
+	uint32_t serial = wlr_seat_client_next_serial(point->client);
 	struct wl_resource *resource;
 	wl_resource_for_each(resource, &point->client->touches) {
 		if (seat_client_from_touch_resource(resource) == NULL) {
diff --git a/types/wlr_data_control_v1.c b/types/wlr_data_control_v1.c
index b23e37ee..d21a6ba1 100644
--- a/types/wlr_data_control_v1.c
+++ b/types/wlr_data_control_v1.c
@@ -343,7 +343,7 @@ static void control_handle_set_selection(struct wl_client *client,
 	}
 
 	if (source == NULL) {
-		wlr_seat_request_set_selection(device->seat, NULL,
+		wlr_seat_request_set_selection(device->seat, NULL, NULL,
 			wl_display_next_serial(device->seat->display));
 
 		return;
@@ -377,7 +377,7 @@ static void control_handle_set_selection(struct wl_client *client,
 
 	source->finalized = true;
 
-	wlr_seat_request_set_selection(device->seat, wlr_source,
+	wlr_seat_request_set_selection(device->seat, NULL, wlr_source,
 		wl_display_next_serial(device->seat->display));
 }
 
@@ -396,7 +396,7 @@ static void control_handle_set_primary_selection(struct wl_client *client,
 	}
 
 	if (source == NULL) {
-		wlr_seat_request_set_primary_selection(device->seat, NULL,
+		wlr_seat_request_set_primary_selection(device->seat, NULL, NULL,
 			wl_display_next_serial(device->seat->display));
 
 		return;
@@ -430,7 +430,7 @@ static void control_handle_set_primary_selection(struct wl_client *client,
 
 	source->finalized = true;
 
-	wlr_seat_request_set_primary_selection(device->seat, wlr_source,
+	wlr_seat_request_set_primary_selection(device->seat, NULL, wlr_source,
 		wl_display_next_serial(device->seat->display));
 }
 
diff --git a/types/wlr_gtk_primary_selection.c b/types/wlr_gtk_primary_selection.c
index 5228014c..fe50972e 100644
--- a/types/wlr_gtk_primary_selection.c
+++ b/types/wlr_gtk_primary_selection.c
@@ -217,7 +217,10 @@ static void device_handle_set_selection(struct wl_client *client,
 		source = &client_source->source;
 	}
 
-	wlr_seat_request_set_primary_selection(device->seat, source, serial);
+	struct wlr_seat_client *seat_client =
+		wlr_seat_client_for_wl_client(device->seat, client);
+
+	wlr_seat_request_set_primary_selection(device->seat, seat_client, source, serial);
 }
 
 static void device_handle_destroy(struct wl_client *client,
diff --git a/types/wlr_primary_selection.c b/types/wlr_primary_selection.c
index 05b74720..f9a03a26 100644
--- a/types/wlr_primary_selection.c
+++ b/types/wlr_primary_selection.c
@@ -42,11 +42,18 @@ void wlr_primary_selection_source_send(
 
 
 void wlr_seat_request_set_primary_selection(struct wlr_seat *seat,
+		struct wlr_seat_client *client,
 		struct wlr_primary_selection_source *source, uint32_t serial) {
+	if (client && !wlr_serial_maybe_valid(&client->serials, serial)) {
+		wlr_log(WLR_DEBUG, "Rejecting set_primary_selection request, "
+			"serial %"PRIu32" was never given to client", serial);
+		return;
+	}
+
 	if (seat->primary_selection_source &&
-			seat->primary_selection_serial - serial < UINT32_MAX / 2) {
+			serial - seat->primary_selection_serial > UINT32_MAX / 2) {
 		wlr_log(WLR_DEBUG, "Rejecting set_primary_selection request, "
-			"invalid serial (%"PRIu32" <= %"PRIu32")",
+			"serial indicates superseded (%"PRIu32" < %"PRIu32")",
 			serial, seat->primary_selection_serial);
 		return;
 	}
diff --git a/types/wlr_primary_selection_v1.c b/types/wlr_primary_selection_v1.c
index 1a6411ea..e3a6620c 100644
--- a/types/wlr_primary_selection_v1.c
+++ b/types/wlr_primary_selection_v1.c
@@ -217,7 +217,10 @@ static void device_handle_set_selection(struct wl_client *client,
 		source = &client_source->source;
 	}
 
-	wlr_seat_request_set_primary_selection(device->seat, source, serial);
+	struct wlr_seat_client *seat_client =
+		wlr_seat_client_for_wl_client(device->seat, client);
+
+	wlr_seat_request_set_primary_selection(device->seat, seat_client, source, serial);
 }
 
 static void device_handle_destroy(struct wl_client *client,
diff --git a/xwayland/selection/incoming.c b/xwayland/selection/incoming.c
index 290af0bf..ceca1190 100644
--- a/xwayland/selection/incoming.c
+++ b/xwayland/selection/incoming.c
@@ -349,7 +349,7 @@ static void xwm_selection_get_targets(struct wlr_xwm_selection *selection) {
 		bool ok = source_get_targets(selection, &source->base.mime_types,
 			&source->mime_types_atoms);
 		if (ok) {
-			wlr_seat_request_set_selection(xwm->seat, &source->base,
+			wlr_seat_request_set_selection(xwm->seat, NULL, &source->base,
 				wl_display_next_serial(xwm->xwayland->wl_display));
 		} else {
 			wlr_data_source_destroy(&source->base);
@@ -424,10 +424,10 @@ int xwm_handle_xfixes_selection_notify(struct wlr_xwm *xwm,
 			// A real X client selection went away, not our
 			// proxy selection
 			if (selection == &xwm->clipboard_selection) {
-				wlr_seat_request_set_selection(xwm->seat, NULL,
+				wlr_seat_request_set_selection(xwm->seat, NULL, NULL,
 					wl_display_next_serial(xwm->xwayland->wl_display));
 			} else if (selection == &xwm->primary_selection) {
-				wlr_seat_request_set_primary_selection(xwm->seat, NULL,
+				wlr_seat_request_set_primary_selection(xwm->seat, NULL, NULL,
 					wl_display_next_serial(xwm->xwayland->wl_display));
 			} else if (selection == &xwm->dnd_selection) {
 				// TODO: DND