1. Scan the WAL log of the old cluster, starting from the point where the new cluster's timeline history forked off from the old cluster. For each WAL record, make a note of the data blocks that are touched. This yields a list of all the data blocks that were changed in the old cluster, after the new cluster forked off.
Suppose that a transaction is open and has written tuples at the point where WAL forks. After WAL forks, the transaction commits. Then, it hints some of the tuples that it wrote. There is no record in WAL that those blocks are changed, but failing to revert them leads to data corruption.
Bummer, you're right. Hmm, if you have checksums enabled, however, we'll WAL log a full-page every time a page is dirtied for setting a hint bit, which fixes the problem. So, there's a caveat with pg_rewind; you must have checksums enabled.
I was quite impressed with the idea, but hint bits indeed are problem. I realised the same issue also applies to the other idea that Fujii-san and others have suggested about waiting for dirty buffers to be written until the WAL is received at the standby. But since that idea would anyways need to be implemented in the core, we could teach SetHintBits() to return false unless the corresponding commit WAL records are written to the standby first.