guessNonExistentKey attempts to perform a map lookup that returns ENOENT. This is necessary on kernels before 4.4.132, since those don't support iterating maps from the start by providing an invalid key pointer.
()
| 1183 | // This is necessary on kernels before 4.4.132, since those don't support |
| 1184 | // iterating maps from the start by providing an invalid key pointer. |
| 1185 | func (m *Map) guessNonExistentKey() ([]byte, error) { |
| 1186 | // Map a protected page and use that as the value pointer. This saves some |
| 1187 | // work copying out the value, which we're not interested in. |
| 1188 | page, err := mmapProtectedPage() |
| 1189 | if err != nil { |
| 1190 | return nil, err |
| 1191 | } |
| 1192 | valuePtr := sys.UnsafeSlicePointer(page) |
| 1193 | |
| 1194 | randKey := make([]byte, int(m.keySize)) |
| 1195 | |
| 1196 | for i := range 4 { |
| 1197 | switch i { |
| 1198 | // For hash maps, the 0 key is less likely to be occupied. They're often |
| 1199 | // used for storing data related to pointers, and their access pattern is |
| 1200 | // generally scattered across the keyspace. |
| 1201 | case 0: |
| 1202 | // An all-0xff key is guaranteed to be out of bounds of any array, since |
| 1203 | // those have a fixed key size of 4 bytes. The only corner case being |
| 1204 | // arrays with 2^32 max entries, but those are prohibitively expensive |
| 1205 | // in many environments. |
| 1206 | case 1: |
| 1207 | for r := range randKey { |
| 1208 | randKey[r] = 0xff |
| 1209 | } |
| 1210 | // Inspired by BCC, 0x55 is an alternating binary pattern (0101), so |
| 1211 | // is unlikely to be taken. |
| 1212 | case 2: |
| 1213 | for r := range randKey { |
| 1214 | randKey[r] = 0x55 |
| 1215 | } |
| 1216 | // Last ditch effort, generate a random key. |
| 1217 | case 3: |
| 1218 | rand.New(rand.NewSource(time.Now().UnixNano())).Read(randKey) |
| 1219 | } |
| 1220 | |
| 1221 | err := m.lookup(randKey, valuePtr, 0) |
| 1222 | if errors.Is(err, ErrKeyNotExist) { |
| 1223 | return randKey, nil |
| 1224 | } |
| 1225 | } |
| 1226 | |
| 1227 | return nil, errors.New("couldn't find non-existing key") |
| 1228 | } |
| 1229 | |
| 1230 | // BatchLookup looks up many elements in a map at once. |
| 1231 | // |