Avoid some other O(N^2) hazards in list manipulation.

tglsfdc · tglsfdc · commit e477642a1ba8 · 2021-11-01T16:24:40.000-04:00
In the same spirit as 6301c3a, fix some more places where we were using list_delete_first() in a loop and thereby risking O(N^2) behavior. It's not clear that the lists manipulated in these spots can get long enough to be really problematic ... but it's not clear that they can't, either, and the fixes are simple enough. As before, back-patch to v13. Discussion: https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com
diff --git a/contrib/pg_trgm/trgm_regexp.c b/contrib/pg_trgm/trgm_regexp.c
@@ -904,6 +904,7 @@ transformGraph(TrgmNFA *trgmNFA)
 	HASHCTL		hashCtl;
 	TrgmStateKey initkey;
 	TrgmState  *initstate;
+	ListCell   *lc;
 
 	/* Initialize this stage's workspace in trgmNFA struct */
 	trgmNFA->queue = NIL;
@@ -934,12 +935,13 @@ transformGraph(TrgmNFA *trgmNFA)
 	/*
 	 * Recursively build the expanded graph by processing queue of states
 	 * (breadth-first search).  getState already put initstate in the queue.
+	 * Note that getState will append new states to the queue within the loop,
+	 * too; this works as long as we don't do repeat fetches using the "lc"
+	 * pointer.
 	 */
-	while (trgmNFA->queue != NIL)
+	foreach(lc, trgmNFA->queue)
 	{
-		TrgmState  *state = (TrgmState *) linitial(trgmNFA->queue);
-
-		trgmNFA->queue = list_delete_first(trgmNFA->queue);
+		TrgmState  *state = (TrgmState *) lfirst(lc);
 
 		/*
 		 * If we overflowed then just mark state as final.  Otherwise do
@@ -963,22 +965,29 @@ transformGraph(TrgmNFA *trgmNFA)
 static void
 processState(TrgmNFA *trgmNFA, TrgmState *state)
 {
+	ListCell   *lc;
+
 	/* keysQueue should be NIL already, but make sure */
 	trgmNFA->keysQueue = NIL;
 
 	/*
 	 * Add state's own key, and then process all keys added to keysQueue until
-	 * queue is empty.  But we can quit if the state gets marked final.
+	 * queue is finished.  But we can quit if the state gets marked final.
 	 */
 	addKey(trgmNFA, state, &state->stateKey);
-	while (trgmNFA->keysQueue != NIL && !(state->flags & TSTATE_FIN))
+	foreach(lc, trgmNFA->keysQueue)
 	{
-		TrgmStateKey *key = (TrgmStateKey *) linitial(trgmNFA->keysQueue);
+		TrgmStateKey *key = (TrgmStateKey *) lfirst(lc);
 
-		trgmNFA->keysQueue = list_delete_first(trgmNFA->keysQueue);
+		if (state->flags & TSTATE_FIN)
+			break;
 		addKey(trgmNFA, state, key);
 	}
 
+	/* Release keysQueue to clean up for next cycle */
+	list_free(trgmNFA->keysQueue);
+	trgmNFA->keysQueue = NIL;
+
 	/*
 	 * Add outgoing arcs only if state isn't final (we have no interest in
 	 * outgoing arcs if we already match)
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
@@ -2610,8 +2610,9 @@ agg_refill_hash_table(AggState *aggstate)
 	if (aggstate->hash_batches == NIL)
 		return false;
 
-	batch = linitial(aggstate->hash_batches);
-	aggstate->hash_batches = list_delete_first(aggstate->hash_batches);
+	/* hash_batches is a stack, with the top item at the end of the list */
+	batch = llast(aggstate->hash_batches);
+	aggstate->hash_batches = list_delete_last(aggstate->hash_batches);
 
 	hash_agg_set_limits(aggstate->hashentrysize, batch->input_card,
 						batch->used_bits, &aggstate->hash_mem_limit,
@@ -3190,7 +3191,7 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
 		new_batch = hashagg_batch_new(tapeset, tapenum, setno,
 									  spill->ntuples[i], cardinality,
 									  used_bits);
-		aggstate->hash_batches = lcons(new_batch, aggstate->hash_batches);
+		aggstate->hash_batches = lappend(aggstate->hash_batches, new_batch);
 		aggstate->hash_batches_used++;
 	}
 
@@ -3205,8 +3206,6 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
 static void
 hashagg_reset_spill_state(AggState *aggstate)
 {
-	ListCell   *lc;
-
 	/* free spills from initial pass */
 	if (aggstate->hash_spills != NULL)
 	{
@@ -3224,13 +3223,7 @@ hashagg_reset_spill_state(AggState *aggstate)
 	}
 
 	/* free batches */
-	foreach(lc, aggstate->hash_batches)
-	{
-		HashAggBatch *batch = (HashAggBatch *) lfirst(lc);
-
-		pfree(batch);
-	}
-	list_free(aggstate->hash_batches);
+	list_free_deep(aggstate->hash_batches);
 	aggstate->hash_batches = NIL;
 
 	/* close tape set */
diff --git a/src/backend/jit/llvm/llvmjit.c b/src/backend/jit/llvm/llvmjit.c
@@ -171,6 +171,7 @@ static void
 llvm_release_context(JitContext *context)
 {
 	LLVMJitContext *llvm_context = (LLVMJitContext *) context;
+	ListCell   *lc;
 
 	/*
 	 * When this backend is exiting, don't clean up LLVM. As an error might
@@ -188,12 +189,9 @@ llvm_release_context(JitContext *context)
 		llvm_context->module = NULL;
 	}
 
-	while (llvm_context->handles != NIL)
+	foreach(lc, llvm_context->handles)
 	{
-		LLVMJitHandle *jit_handle;
-
-		jit_handle = (LLVMJitHandle *) linitial(llvm_context->handles);
-		llvm_context->handles = list_delete_first(llvm_context->handles);
+		LLVMJitHandle *jit_handle = (LLVMJitHandle *) lfirst(lc);
 
 #if LLVM_VERSION_MAJOR > 11
 		{
@@ -221,6 +219,8 @@ llvm_release_context(JitContext *context)
 
 		pfree(jit_handle);
 	}
+	list_free(llvm_context->handles);
+	llvm_context->handles = NIL;
 }
 
 /*

Original file line number	Diff line number	Diff line change
`@@ -171,6 +171,7 @@ static void`
`171`	`171`	`llvm_release_context(JitContext *context)`
`172`	`172`	`{`
`173`	`173`	`LLVMJitContext llvm_context = (LLVMJitContext ) context;`
	`174`	`+ ListCell *lc;`
`174`	`175`
`175`	`176`	`/*`
`176`	`177`	`* When this backend is exiting, don't clean up LLVM. As an error might`
`@@ -188,12 +189,9 @@ llvm_release_context(JitContext *context)`
`188`	`189`	`llvm_context->module = NULL;`
`189`	`190`	`}`
`190`	`191`
`191`		`- while (llvm_context->handles != NIL)`
	`192`	`+ foreach(lc, llvm_context->handles)`
`192`	`193`	`{`
`193`		`- LLVMJitHandle *jit_handle;`
`194`		`-`
`195`		`- jit_handle = (LLVMJitHandle *) linitial(llvm_context->handles);`
`196`		`- llvm_context->handles = list_delete_first(llvm_context->handles);`
	`194`	`+ LLVMJitHandle jit_handle = (LLVMJitHandle ) lfirst(lc);`
`197`	`195`
`198`	`196`	`#if LLVM_VERSION_MAJOR > 11`
`199`	`197`	`{`
`@@ -221,6 +219,8 @@ llvm_release_context(JitContext *context)`
`221`	`219`
`222`	`220`	`pfree(jit_handle);`
`223`	`221`	`}`
	`222`	`+ list_free(llvm_context->handles);`
	`223`	`+ llvm_context->handles = NIL;`
`224`	`224`	`}`
`225`	`225`
`226`	`226`	`/*`