<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/60694>60694</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
Clang Static Analyzer generates false positive because it does not understand copies via C pointer dereferences
</td>
</tr>
<tr>
<th>Labels</th>
<td>
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
ryao
</td>
</tr>
</table>
<pre>
The last time I tried filing a bug report, I made a minimal test case that was so minimal that it lost a key nuance that was important for demonstrating the issue in Clang's static analyzer, so this time, I have am providing this example which has all of the code that is relevant to the report and I did not try to reduce the example any further:
```
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#define ASSERT assert
typedef unsigned long ulong_t;
struct avl_node {
struct avl_node *avl_child[2]; /* left/right children nodes */
uintptr_t avl_pcb; /* parent, child_index, balance */
};
/*
* macros to extract/set fields in avl_pcb
*
* pointer to the parent of the current node is the high order bits
*/
#define AVL_XPARENT(n) ((struct avl_node *)((n)->avl_pcb & ~7))
#define AVL_SETPARENT(n, p) \
((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p)))
/*
* index of this node in its parent's avl_child[]: bit #2
*/
#define AVL_XCHILD(n) (((n)->avl_pcb >> 2) & 1)
#define AVL_SETCHILD(n, c) \
((n)->avl_pcb = (uintptr_t)(((n)->avl_pcb & ~4) | ((c) << 2)))
/*
* balance indication for a node, lowest 2 bits. A valid balance is
* -1, 0, or +1, and is encoded by adding 1 to the value to get the
* unsigned values of 0, 1, 2.
*/
#define AVL_XBALANCE(n) ((int)(((n)->avl_pcb & 3) - 1))
#define AVL_SETBALANCE(n, b) \
((n)->avl_pcb = (uintptr_t)((((n)->avl_pcb & ~3) | ((b) + 1))))
/*
* switch between a node and data pointer for a given tree
* the value of "o" is tree->avl_offset
*/
#define AVL_NODE2DATA(n, o) ((void *)((uintptr_t)(n) - (o)))
#define AVL_DATA2NODE(d, o) ((struct avl_node *)((uintptr_t)(d) + (o)))
/*
* The tree structure. The fields avl_root, avl_compar, and avl_offset come
* first since they are needed for avl_find(). We want them to fit into
* a single 64 byte cache line to make avl_find() as fast as possible.
*/
struct avl_tree {
struct avl_node *avl_root; /* root node in tree */
int (*avl_compar)(const void *, const void *);
size_t avl_offset; /* offsetof(type, avl_link_t field) */
ulong_t avl_numnodes; /* number of nodes in the tree */
#ifndef _KERNEL
size_t avl_pad; /* For backwards ABI compatibility. */
#endif
};
typedef struct avl_tree avl_tree_t;
typedef struct avl_node avl_node_t;
extern int
avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance);
void
avl_remove(avl_tree_t *tree, void *data)
{
avl_node_t *delete;
avl_node_t *parent;
avl_node_t *node;
avl_node_t tmp;
int old_balance;
int new_balance;
int left;
int right;
int which_child;
size_t off = tree->avl_offset;
delete = AVL_DATA2NODE(data, off);
/*
* Deletion is easiest with a node that has at most 1 child.
* We swap a node with 2 children with a sequentially valued
* neighbor node. That node will have at most 1 child. Note this
* has no effect on the ordering of the remaining nodes.
*
* As an optimization, we choose the greater neighbor if the tree
* is right heavy, otherwise the left neighbor. This reduces the
* number of rotations needed.
*/
if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) {
/*
* choose node to swap from whichever side is taller
*/
old_balance = AVL_XBALANCE(delete);
left = (old_balance > 0);
right = 1 - left;
/*
* get to the previous value'd node
* (down 1 left, as far as possible right)
*/
for (node = delete->avl_child[left];
node->avl_child[right] != NULL;
node = node->avl_child[right])
;
/*
* create a temp placeholder for 'node'
* move 'node' to delete's spot in the tree
*/
tmp = *node;
*node = *delete;
if (node->avl_child[left] == node)
node->avl_child[left] = &tmp;
parent = AVL_XPARENT(node);
if (parent != NULL)
parent->avl_child[AVL_XCHILD(node)] = node;
else
tree->avl_root = node;
AVL_SETPARENT(node->avl_child[left], node);
AVL_SETPARENT(node->avl_child[right], node);
/*
* Put tmp where node used to be (just temporary).
* It always has a parent and at most 1 child.
*/
delete = &tmp;
parent = AVL_XPARENT(delete);
parent->avl_child[AVL_XCHILD(delete)] = delete;
which_child = (delete->avl_child[1] != 0);
if (delete->avl_child[which_child] != NULL)
AVL_SETPARENT(delete->avl_child[which_child], delete);
}
/*
* Here we know "delete" is at least partially a leaf node. It can
* be easily removed from the tree.
*/
ASSERT(tree->avl_numnodes > 0);
--tree->avl_numnodes;
parent = AVL_XPARENT(delete);
which_child = AVL_XCHILD(delete);
if (delete->avl_child[0] != NULL)
node = delete->avl_child[0];
else
node = delete->avl_child[1];
/*
* Connect parent directly to node (leaving out delete).
*/
if (node != NULL) {
AVL_SETPARENT(node, parent);
AVL_SETCHILD(node, which_child);
}
if (parent == NULL) {
tree->avl_root = node;
return;
}
parent->avl_child[which_child] = node;
/*
* Since the subtree is now shorter, begin adjusting parent balances
* and performing any needed rotations.
*/
do {
/*
* Move up the tree and adjust the balance
*
* Capture the parent and which_child values for the next
* iteration before any rotations occur.
*/
node = parent;
old_balance = AVL_XBALANCE(node);
new_balance = old_balance - (which_child ? 1 : -1);
parent = AVL_XPARENT(node);
which_child = AVL_XCHILD(node);
/*
* If a node was in perfect balance but isn't anymore then
* we can stop, since the height didn't change above this point
* due to a deletion.
*/
if (old_balance == 0) {
AVL_SETBALANCE(node, new_balance);
break;
}
/*
* If the new balance is zero, we don't need to rotate
* else
* need a rotation to fix the balance.
* If the rotation doesn't change the height
* of the sub-tree we have finished adjusting.
*/
if (new_balance == 0)
AVL_SETBALANCE(node, new_balance);
else if (!avl_rotation(tree, node, new_balance))
break;
} while (parent != NULL);
}
```
Clang's static analyzer reports a false positive on this:
```
$ clang --analyze -S /tmp/bug.c
/tmp/bug.c:129:3: warning: Access to field 'avl_pcb' results in a dereference of a null pointer [core.NullDereference]
AVL_SETPARENT(node->avl_child[right], node);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/bug.c:21:20: note: expanded from macro 'AVL_SETPARENT'
((n)->avl_pcb = (((n)->avl_pcb & 7) | (uintptr_t)(p)))
^~~~~~~~~~~~
1 warning generated.
```
If you replace `*node = *delete;` with `memcpy(node, delete, sizeof (*node));`, the false positive disappears. Based on this, I believe that Clang's static analyzer does not understand memory copies via C pointer dereferences. This should be a bug in the analyzer.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0Wk9z4ziu_zTKBRWXLSf-c8jBcZKa1OvXb2q6387eUpQIWZyWSC1J2e0-zGffAknJsizF6Z2drpTblkgQBH4EfoDEjBE7ifgQ3T9G9083rLa50g_6yNRNovjx4WuOUDBjwYoS4RWsFsghE4WQO2CQ1DvQWClto3gLr1AyjsCgFFKUrACLxkLKDILNmYUDM2DU6S5dExYKZSww-IZHkDWTaWe0KEk2kxYypYFjqaSxmlla3eYIwpgaQUjYFkzuonhpwFhmRQpMsuL4AzXpZRTYXBi3B69nzvYIrIRKq73gXpowgN9ZWRUIh1ykOeTMACsKUJlbK1U8aCYMaCxwT3pZ5W56IwCTHF6BCw5SWbD6SPc18tptCtsFmDxCVmubo47mm2j6FE2bz8U0_Pmf8VzItKg5QjTfMmNQ20kezZ-HbhvLOWbv3RbybHYziGMmJMLmy5fn376CX6U7xB4r5JhBLR1cOBRK7uD0r6bfbzaaP3ZnGavr1ALbF2-SbBct29vri3vxhr6nuSh4dP8YR_dPTto6il-ieAMFZjaKX7TY5RbcKI0SaKqhuTSqEV0LaSur37z0Kk2CoFZWxTRKB1gn6E1Ijt_pZ8IKB78zgcun3ra8FP-dhkLJUq0MeRq_W81SUtSghUxgwQ2hs1GkndOZXSkhLeoGSF65FnO1dj-djQjBOUIudjkozVFDIqzpCG11bjwaTdebf3x6--evm9-eP3-N4pWM4nVji1UUrwbcQCPcPRp7G82fg_IQxQv4c-lur4fX-fL8tbvSFqrTct2_-23rrJGl5k_g74zoQWpAtNzSqNbfXvMqaNgqOew053RvZmGCfSUIa1p4LA10IekQuSGTQxTP44-YffvL66enAasP7vg5mj9D7PYVL2D2npE7creQ_jUb96z3juvvOjaP4lXqfs630Xzr1P6AzZvzJSQXKbNCSRfWmTM_7aVQB8oYsQP2BDawZ4Xgp3kdsMPtjGZM6UNpiOJH95sCMAVySdGaQ3IExl18nzUHbM-KGunHDi1d6Ihsw5sbYwgdTr6THE8-4vLHzafN5-3zgNOFvGriOZn01vv-HfefrbGF5G8AwBgG5ucYSDxcH1uVLzEwjARzEDbNIUF7QJQBAc55nFnWxkSPjp3YowSrseurkytVBlEcqyiOXYTUiI3aKssM2g-47fP_PT3HT5uvm8amKtjU7XKvBD-LjD2TSe-2KF6pvg1669ASMS0WxSt-sc57wbi3JG8MP7TosMmJyZFxwC9Ta5y4ayFL0apaKZcWXdhTZcV0c6RO1oRUlV0_ZEIbC0Z42oZHYBpBItLpc-7bF2-ZkNxtYz0B-B3h4IhTjiUdw0xYENKqjkxG8nYFwuIOkqNFSFlKPJQ4ilVQsm_YkwvMQEY0lRmolDEiKXDovHZM7GzxAUrijNKlInShTRheyjkBEdL687HpGpLclhJ9hROettC_su6QjbURPzDQmADlHpPxV1UWxSuiaI3vCiG_vQX-4YFyTpA8W_M7rUtHovqSZV0mqOlseY5FW20A1DtJIpPEDd_-5_m3z8-fhpSvGD_Jb5d4URoSln47MM0NbB5fwZnKikQUwh4n_XVQcpGNkbKGofYd3HzpkNOBoT76hC8XPNZ_4neLWhJU_W-PDevSWBSvTguR3i5YBW94mXS1SXMEkJDTzj1On4SFzgpYqj2Oym-AQ1HzFAA6oD5XgGOBFrsQO78fqM_ofbeB4bu2rLp3aIuq4G_NNnu3JB7Gbjmm37vmaH__oivSAj27PDQqy1yGG8gHfe-uvVnc8Iso7Qy7JXGXrmqx3P504euJxBG5ISLCjCBKcxA2b9KcqyFdcWmhpNp35guRybmY3xHMgVXNLCchPtU-QaLBf9UorWBFcfQJkZ-LkSh2eaK0k0Ihn9lGYFGEQrinB3xWFh0xPhdFOksFmGWYWlA-JLhKhBhWKFk0lkxIuuAix_mmzuVtDDAJqrKiFD_CQdrCASHNlTK-Yt5pZEQF2m2IrI1E59KoKnflYY5sf3ROo_r6IIIkAlYrhgzhyngqzc2JB7ZWa-Nfc8ZNyGq9DXXjPhGRlQdTA7mmephG98S2ZoSxz___6RPRKWJUw6NnvdGedV1g7wJ-jfbBfh5tysMo06r0Zwb3qMGIUFGyokDdl9DdVjRdd05ye0o6VDeElfPkFU3XzuKBZp6LeCZi3R_uvUfjZ3DbjwNX9-zofKihNe6Fqo0_D1G85L7C6E8h1dVBwiy0F7aeRuguiwix50SuRkyUuSJk5ZnD_GnEsW6d-6fexp12_aF-3R4OevMAoF3wPRk99envJyybuiMIDCyWFVQFSzFXBQ_8PIqXPq8tLyZS6urcJ_c0UFkaMJWyXV5xxcC2rAKW-mmou4FNa4_BdNee0iFrBefQ7Magl4a7MpHO9XkqPM0OrZ32AJ16JWGlIUWbSWfBoKeTH9PX6rwFEZYIWvYTeTRdY2GwJ7ebOx3rHZl60fsZtxEdsuHtfkTICc9DUq4C-dfa8RQ45KhDdKwNcsJlQkBd_VEb61CuNNNHqlcuZLxaYMWBHY3P4E2_zhVJY-l8GNAd1nEBmnfhMhZuPwCD09QAhMEj0mFWTfi-nqcGAvp7CbHL3i6SXQ-HfWh8RCJBZNhQy6eBBsUwk_uFcHJA-CbVAaI4bgS6TgMjrko1Z8V04F-MrmSBab1aSJk8F5igY4TFETyx5z4tNyFwnFv41jzVeZ0z2RRvgwn19nZoaHfEzwGsD4oRXHVJ-k_woZ7Tr6TRaS-H9mPXlemz8-nvAGCrpCSuG0zFhcbUFu6pTugRrApke0d_a3sC3DWSGCaPEbyxeOh66qE9PRI_zwP-9qxKGj0IvVzj89-IXh9NChptreXYgsOxqh8ULiVf9diXphMFpk5cC8C19w9gcqWtfx6Y4E5IYJzCPbku7DvQ017RQ5G9Qp0pXbpnnvLYtLfaymDc21z9FG__XyJMdXVqtbi0wn1ayrFtGvQTS1_OllW21th9oESSukc4tLiJwdEoid_thRhhUfs2fYKZ0v6x5akeUmla62tZrj2Kl72F64XFMFPoNA_cpK4Q14Y9D1UvMINo7h8YDKfMD1Oyd2Pgf0BIXrO2umeux0ZAo3jTbCepLQgjo3hJHjyWyjtVXkiioplJMFZV7ol3ewpydFUVF9xLSXMmdwgsIai5Z1-u2X4hkPuHJMzHNKHkNUf7ENJzaEMM-kFk8GFGiFjd3tCFB6LpOtHIvvUv95P6-0b3iD90HizBD9QqdB-48qaiY-6e3xPiL6vHftIJ3RbkwNpD4hvc37uHd4BShsZJM4crNGfOOvnxYm5oupg6ceme1HctnUxIYXLkpyj3Mf_1zlZL7P4bviODgV8mime9_mnT0RyRdKHCJQqWTxTgChyvmtrRLVp6L1u4z9FXScJLHsT6M0Z7qZQRVuzRt8KEufYqxx2kJBtub4NIuP0CUfxC3D9-SerdJG2Gnl2bb2ak_WZOYezAtBRyR183aYrGeIwhhaR42bxpEC9Bo6kL698_AI4aM9RIflUu6tRF0T5ni-4fU6Vx8rkuiqfTSKJJTh_4q8UZRPfPf37434gRyJmbeEo7l4qKlg3g94pJ3tBo9yIGWaGnbuhMNG-r_P3vHMDov3M7-NGzxqewQ0kZ99RkHMLnawZHVRMYC0andDEdbXsspr5NHC2mJZZpdewc1YarUrL4gSocy03jOe-8hXv-TRGmh3guDKsqZNpM4JFREd2cAfd-VYKFwH1odY8fKIp07k2pWnLUxhJJKbFU-gipqgQa2AsG2xanHRSb0ME1uaoLToWVfxstNJSaJSY3_GHO1_M1u8GH2WK5iOfL5XJ2kz_EsyyN72f3M2TJ6o5xxu-nK85wep9N-QxnN-IhnsbzaTyL49l8MZtNFovVarZczOd8iovZ3Ty6m2LJRDEpin05UXp3415He1hMF-u7m4IlWJjmxTr9QINuk3pnortpIYw1p2lW2AIfnJngizfRpjFRAwnT90CCKaspoNpBM161302ti4fc2sqFLUqVLzth8zqZpKqM4hfSLvx3W2n1B7r3mtwOTRS_uE3-OwAA__8K46UT">