Avoid O(N^2) behavior in SyncPostCheckpoint().

As in commits 6301c3ada and e9d9ba2a4, avoid doing repetitive
list_delete_first() operations, since that would be expensive when
there are many files waiting to be unlinked.  This is a slightly
larger change than in those cases.  We have to keep the list state
valid for calls to AbsorbSyncRequests(), so it's necessary to invent a
"canceled" field instead of immediately deleting PendingUnlinkEntry
entries.  Also, because we might not be able to process all the
entries, we need a new list primitive list_delete_first_n().

list_delete_first_n() is almost list_copy_tail(), but it modifies the
input List instead of making a new copy.  I found a couple of existing
uses of the latter that could profitably use the new function.  (There
might be more, but the other callers look like they probably shouldn't
overwrite the input List.)

As before, back-patch to v13.

Discussion: https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com

1 files changed, 34 insertions, 12 deletions

diff --git a/src/backend/storage/sync/sync.c b/src/backend/storage/sync/sync.c
index bc3ceb27125..a12b3572759 100644
--- a/src/backend/storage/sync/sync.c
+++ b/src/backend/storage/sync/sync.c
@@ -69,6 +69,7 @@ typedef struct
 {
 	FileTag		tag;			/* identifies handler and file */
 	CycleCtr	cycle_ctr;		/* checkpoint_cycle_ctr when request was made */
+	bool		canceled;		/* true if request has been canceled */
 } PendingUnlinkEntry;
 
 static HTAB *pendingOps = NULL;
@@ -195,13 +196,18 @@ void
 SyncPostCheckpoint(void)
 {
 	int			absorb_counter;
+	ListCell   *lc;
 
 	absorb_counter = UNLINKS_PER_ABSORB;
-	while (pendingUnlinks != NIL)
+	foreach(lc, pendingUnlinks)
 	{
-		PendingUnlinkEntry *entry = (PendingUnlinkEntry *) linitial(pendingUnlinks);
+		PendingUnlinkEntry *entry = (PendingUnlinkEntry *) lfirst(lc);
 		char		path[MAXPGPATH];
 
+		/* Skip over any canceled entries */
+		if (entry->canceled)
+			continue;
+
 		/*
 		 * New entries are appended to the end, so if the entry is new we've
 		 * reached the end of old entries.
@@ -231,15 +237,13 @@ SyncPostCheckpoint(void)
 						 errmsg("could not remove file \"%s\": %m", path)));
 		}
 
-		/* And remove the list entry */
-		pendingUnlinks = list_delete_first(pendingUnlinks);
-		pfree(entry);
+		/* Mark the list entry as canceled, just in case */
+		entry->canceled = true;
 
 		/*
 		 * As in ProcessSyncRequests, we don't want to stop absorbing fsync
 		 * requests for a long time when there are many deletions to be done.
-		 * We can safely call AbsorbSyncRequests() at this point in the loop
-		 * (note it might try to delete list entries).
+		 * We can safely call AbsorbSyncRequests() at this point in the loop.
 		 */
 		if (--absorb_counter <= 0)
 		{
@@ -247,6 +251,26 @@ SyncPostCheckpoint(void)
 			absorb_counter = UNLINKS_PER_ABSORB;
 		}
 	}
+
+	/*
+	 * If we reached the end of the list, we can just remove the whole list
+	 * (remembering to pfree all the PendingUnlinkEntry objects).  Otherwise,
+	 * we must keep the entries at or after "lc".
+	 */
+	if (lc == NULL)
+	{
+		list_free_deep(pendingUnlinks);
+		pendingUnlinks = NIL;
+	}
+	else
+	{
+		int			ntodelete = list_cell_number(pendingUnlinks, lc);
+
+		for (int i = 0; i < ntodelete; i++)
+			pfree(list_nth(pendingUnlinks, i));
+
+		pendingUnlinks = list_delete_first_n(pendingUnlinks, ntodelete);
+	}
 }
 
 /*
@@ -486,17 +510,14 @@ RememberSyncRequest(const FileTag *ftag, SyncRequestType type)
 				entry->canceled = true;
 		}
 
-		/* Remove matching unlink requests */
+		/* Cancel matching unlink requests */
 		foreach(cell, pendingUnlinks)
 		{
 			PendingUnlinkEntry *entry = (PendingUnlinkEntry *) lfirst(cell);
 
 			if (entry->tag.handler == ftag->handler &&
 				syncsw[ftag->handler].sync_filetagmatches(ftag, &entry->tag))
-			{
-				pendingUnlinks = foreach_delete_current(pendingUnlinks, cell);
-				pfree(entry);
-			}
+				entry->canceled = true;
 		}
 	}
 	else if (type == SYNC_UNLINK_REQUEST)
@@ -508,6 +529,7 @@ RememberSyncRequest(const FileTag *ftag, SyncRequestType type)
 		entry = palloc(sizeof(PendingUnlinkEntry));
 		entry->tag = *ftag;
 		entry->cycle_ctr = checkpoint_cycle_ctr;
+		entry->canceled = false;
 
 		pendingUnlinks = lappend(pendingUnlinks, entry);