allocator.go 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637
  1. package ipam
  2. import (
  3. "fmt"
  4. "net"
  5. "sort"
  6. "sync"
  7. "github.com/docker/docker/libnetwork/bitseq"
  8. "github.com/docker/docker/libnetwork/datastore"
  9. "github.com/docker/docker/libnetwork/discoverapi"
  10. "github.com/docker/docker/libnetwork/ipamapi"
  11. "github.com/docker/docker/libnetwork/ipamutils"
  12. "github.com/docker/docker/libnetwork/types"
  13. "github.com/sirupsen/logrus"
  14. )
  15. const (
  16. localAddressSpace = "LocalDefault"
  17. globalAddressSpace = "GlobalDefault"
  18. // datastore keyes for ipam objects
  19. dsConfigKey = "ipam/" + ipamapi.DefaultIPAM + "/config"
  20. dsDataKey = "ipam/" + ipamapi.DefaultIPAM + "/data"
  21. )
  22. // Allocator provides per address space ipv4/ipv6 book keeping
  23. type Allocator struct {
  24. // Predefined pools for default address spaces
  25. // Separate from the addrSpace because they should not be serialized
  26. predefined map[string][]*net.IPNet
  27. predefinedStartIndices map[string]int
  28. // The (potentially serialized) address spaces
  29. addrSpaces map[string]*addrSpace
  30. // stores []datastore.Datastore
  31. // Allocated addresses in each address space's subnet
  32. addresses map[SubnetKey]*bitseq.Handle
  33. sync.Mutex
  34. }
  35. // NewAllocator returns an instance of libnetwork ipam
  36. func NewAllocator(lcDs, glDs datastore.DataStore) (*Allocator, error) {
  37. a := &Allocator{}
  38. // Load predefined subnet pools
  39. a.predefined = map[string][]*net.IPNet{
  40. localAddressSpace: ipamutils.GetLocalScopeDefaultNetworks(),
  41. globalAddressSpace: ipamutils.GetGlobalScopeDefaultNetworks(),
  42. }
  43. // Initialize asIndices map
  44. a.predefinedStartIndices = make(map[string]int)
  45. // Initialize bitseq map
  46. a.addresses = make(map[SubnetKey]*bitseq.Handle)
  47. // Initialize address spaces
  48. a.addrSpaces = make(map[string]*addrSpace)
  49. for _, aspc := range []struct {
  50. as string
  51. ds datastore.DataStore
  52. }{
  53. {localAddressSpace, lcDs},
  54. {globalAddressSpace, glDs},
  55. } {
  56. a.initializeAddressSpace(aspc.as, aspc.ds)
  57. }
  58. return a, nil
  59. }
  60. func (a *Allocator) refresh(as string) error {
  61. aSpace, err := a.getAddressSpaceFromStore(as)
  62. if err != nil {
  63. return types.InternalErrorf("error getting pools config from store: %v", err)
  64. }
  65. if aSpace == nil {
  66. return nil
  67. }
  68. a.Lock()
  69. a.addrSpaces[as] = aSpace
  70. a.Unlock()
  71. return nil
  72. }
  73. func (a *Allocator) updateBitMasks(aSpace *addrSpace) error {
  74. var inserterList []func() error
  75. aSpace.Lock()
  76. for k, v := range aSpace.subnets {
  77. if v.Range == nil {
  78. kk := k
  79. vv := v
  80. inserterList = append(inserterList, func() error { return a.insertBitMask(kk, vv.Pool) })
  81. }
  82. }
  83. aSpace.Unlock()
  84. // Add the bitmasks (data could come from datastore)
  85. for _, f := range inserterList {
  86. if err := f(); err != nil {
  87. return err
  88. }
  89. }
  90. return nil
  91. }
  92. // Checks for and fixes damaged bitmask.
  93. func (a *Allocator) checkConsistency(as string) {
  94. var sKeyList []SubnetKey
  95. // Retrieve this address space's configuration and bitmasks from the datastore
  96. a.refresh(as)
  97. a.Lock()
  98. aSpace, ok := a.addrSpaces[as]
  99. a.Unlock()
  100. if !ok {
  101. return
  102. }
  103. a.updateBitMasks(aSpace)
  104. aSpace.Lock()
  105. for sk, pd := range aSpace.subnets {
  106. if pd.Range != nil {
  107. continue
  108. }
  109. sKeyList = append(sKeyList, sk)
  110. }
  111. aSpace.Unlock()
  112. for _, sk := range sKeyList {
  113. a.Lock()
  114. bm := a.addresses[sk]
  115. a.Unlock()
  116. if err := bm.CheckConsistency(); err != nil {
  117. logrus.Warnf("Error while running consistency check for %s: %v", sk, err)
  118. }
  119. }
  120. }
  121. func (a *Allocator) initializeAddressSpace(as string, ds datastore.DataStore) error {
  122. scope := ""
  123. if ds != nil {
  124. scope = ds.Scope()
  125. }
  126. a.Lock()
  127. if currAS, ok := a.addrSpaces[as]; ok {
  128. if currAS.ds != nil {
  129. a.Unlock()
  130. return types.ForbiddenErrorf("a datastore is already configured for the address space %s", as)
  131. }
  132. }
  133. a.addrSpaces[as] = &addrSpace{
  134. subnets: map[SubnetKey]*PoolData{},
  135. id: dsConfigKey + "/" + as,
  136. scope: scope,
  137. ds: ds,
  138. alloc: a,
  139. }
  140. a.Unlock()
  141. a.checkConsistency(as)
  142. return nil
  143. }
  144. // DiscoverNew informs the allocator about a new global scope datastore
  145. func (a *Allocator) DiscoverNew(dType discoverapi.DiscoveryType, data interface{}) error {
  146. if dType != discoverapi.DatastoreConfig {
  147. return nil
  148. }
  149. dsc, ok := data.(discoverapi.DatastoreConfigData)
  150. if !ok {
  151. return types.InternalErrorf("incorrect data in datastore update notification: %v", data)
  152. }
  153. ds, err := datastore.NewDataStoreFromConfig(dsc)
  154. if err != nil {
  155. return err
  156. }
  157. return a.initializeAddressSpace(globalAddressSpace, ds)
  158. }
  159. // DiscoverDelete is a notification of no interest for the allocator
  160. func (a *Allocator) DiscoverDelete(dType discoverapi.DiscoveryType, data interface{}) error {
  161. return nil
  162. }
  163. // GetDefaultAddressSpaces returns the local and global default address spaces
  164. func (a *Allocator) GetDefaultAddressSpaces() (string, string, error) {
  165. return localAddressSpace, globalAddressSpace, nil
  166. }
  167. // RequestPool returns an address pool along with its unique id.
  168. // addressSpace must be a valid address space name and must not be the empty string.
  169. // If pool is the empty string then the default predefined pool for addressSpace will be used, otherwise pool must be a valid IP address and length in CIDR notation.
  170. // If subPool is not empty, it must be a valid IP address and length in CIDR notation which is a sub-range of pool.
  171. // subPool must be empty if pool is empty.
  172. func (a *Allocator) RequestPool(addressSpace, pool, subPool string, options map[string]string, v6 bool) (string, *net.IPNet, map[string]string, error) {
  173. logrus.Debugf("RequestPool(%s, %s, %s, %v, %t)", addressSpace, pool, subPool, options, v6)
  174. k, nw, ipr, err := a.parsePoolRequest(addressSpace, pool, subPool, v6)
  175. if err != nil {
  176. return "", nil, nil, types.InternalErrorf("failed to parse pool request for address space %q pool %q subpool %q: %v", addressSpace, pool, subPool, err)
  177. }
  178. pdf := k == nil
  179. retry:
  180. if pdf {
  181. if nw, err = a.getPredefinedPool(addressSpace, v6); err != nil {
  182. return "", nil, nil, err
  183. }
  184. k = &SubnetKey{AddressSpace: addressSpace, Subnet: nw.String()}
  185. }
  186. if err := a.refresh(addressSpace); err != nil {
  187. return "", nil, nil, err
  188. }
  189. aSpace, err := a.getAddrSpace(addressSpace)
  190. if err != nil {
  191. return "", nil, nil, err
  192. }
  193. insert, err := aSpace.updatePoolDBOnAdd(*k, nw, ipr, pdf)
  194. if err != nil {
  195. if _, ok := err.(types.MaskableError); ok {
  196. logrus.Debugf("Retrying predefined pool search: %v", err)
  197. goto retry
  198. }
  199. return "", nil, nil, err
  200. }
  201. if err := a.writeToStore(aSpace); err != nil {
  202. if _, ok := err.(types.RetryError); !ok {
  203. return "", nil, nil, types.InternalErrorf("pool configuration failed because of %s", err.Error())
  204. }
  205. goto retry
  206. }
  207. return k.String(), nw, nil, insert()
  208. }
  209. // ReleasePool releases the address pool identified by the passed id
  210. func (a *Allocator) ReleasePool(poolID string) error {
  211. logrus.Debugf("ReleasePool(%s)", poolID)
  212. k := SubnetKey{}
  213. if err := k.FromString(poolID); err != nil {
  214. return types.BadRequestErrorf("invalid pool id: %s", poolID)
  215. }
  216. retry:
  217. if err := a.refresh(k.AddressSpace); err != nil {
  218. return err
  219. }
  220. aSpace, err := a.getAddrSpace(k.AddressSpace)
  221. if err != nil {
  222. return err
  223. }
  224. remove, err := aSpace.updatePoolDBOnRemoval(k)
  225. if err != nil {
  226. return err
  227. }
  228. if err = a.writeToStore(aSpace); err != nil {
  229. if _, ok := err.(types.RetryError); !ok {
  230. return types.InternalErrorf("pool (%s) removal failed because of %v", poolID, err)
  231. }
  232. goto retry
  233. }
  234. return remove()
  235. }
  236. // Given the address space, returns the local or global PoolConfig based on whether the
  237. // address space is local or global. AddressSpace locality is registered with IPAM out of band.
  238. func (a *Allocator) getAddrSpace(as string) (*addrSpace, error) {
  239. a.Lock()
  240. defer a.Unlock()
  241. aSpace, ok := a.addrSpaces[as]
  242. if !ok {
  243. return nil, types.BadRequestErrorf("cannot find address space %s (most likely the backing datastore is not configured)", as)
  244. }
  245. return aSpace, nil
  246. }
  247. // parsePoolRequest parses and validates a request to create a new pool under addressSpace and returns
  248. // a SubnetKey, network and range describing the request.
  249. func (a *Allocator) parsePoolRequest(addressSpace, pool, subPool string, v6 bool) (*SubnetKey, *net.IPNet, *AddressRange, error) {
  250. var (
  251. nw *net.IPNet
  252. ipr *AddressRange
  253. err error
  254. )
  255. if addressSpace == "" {
  256. return nil, nil, nil, ipamapi.ErrInvalidAddressSpace
  257. }
  258. if pool == "" && subPool != "" {
  259. return nil, nil, nil, ipamapi.ErrInvalidSubPool
  260. }
  261. if pool == "" {
  262. return nil, nil, nil, nil
  263. }
  264. if _, nw, err = net.ParseCIDR(pool); err != nil {
  265. return nil, nil, nil, ipamapi.ErrInvalidPool
  266. }
  267. if subPool != "" {
  268. if ipr, err = getAddressRange(subPool, nw); err != nil {
  269. return nil, nil, nil, err
  270. }
  271. }
  272. return &SubnetKey{AddressSpace: addressSpace, Subnet: nw.String(), ChildSubnet: subPool}, nw, ipr, nil
  273. }
  274. func (a *Allocator) insertBitMask(key SubnetKey, pool *net.IPNet) error {
  275. //logrus.Debugf("Inserting bitmask (%s, %s)", key.String(), pool.String())
  276. store := a.getStore(key.AddressSpace)
  277. ipVer := getAddressVersion(pool.IP)
  278. ones, bits := pool.Mask.Size()
  279. numAddresses := uint64(1 << uint(bits-ones))
  280. // Allow /64 subnet
  281. if ipVer == v6 && numAddresses == 0 {
  282. numAddresses--
  283. }
  284. // Generate the new address masks. AddressMask content may come from datastore
  285. h, err := bitseq.NewHandle(dsDataKey, store, key.String(), numAddresses)
  286. if err != nil {
  287. return err
  288. }
  289. // Do not let network identifier address be reserved
  290. // Do the same for IPv6 so that bridge ip starts with XXXX...::1
  291. h.Set(0)
  292. // Do not let broadcast address be reserved
  293. if ipVer == v4 {
  294. h.Set(numAddresses - 1)
  295. }
  296. a.Lock()
  297. a.addresses[key] = h
  298. a.Unlock()
  299. return nil
  300. }
  301. func (a *Allocator) retrieveBitmask(k SubnetKey, n *net.IPNet) (*bitseq.Handle, error) {
  302. a.Lock()
  303. bm, ok := a.addresses[k]
  304. a.Unlock()
  305. if !ok {
  306. logrus.Debugf("Retrieving bitmask (%s, %s)", k.String(), n.String())
  307. if err := a.insertBitMask(k, n); err != nil {
  308. return nil, types.InternalErrorf("could not find bitmask in datastore for %s", k.String())
  309. }
  310. a.Lock()
  311. bm = a.addresses[k]
  312. a.Unlock()
  313. }
  314. return bm, nil
  315. }
  316. func (a *Allocator) getPredefineds(as string) []*net.IPNet {
  317. a.Lock()
  318. defer a.Unlock()
  319. p := a.predefined[as]
  320. i := a.predefinedStartIndices[as]
  321. // defensive in case the list changed since last update
  322. if i >= len(p) {
  323. i = 0
  324. }
  325. return append(p[i:], p[:i]...)
  326. }
  327. func (a *Allocator) updateStartIndex(as string, amt int) {
  328. a.Lock()
  329. i := a.predefinedStartIndices[as] + amt
  330. if i < 0 || i >= len(a.predefined[as]) {
  331. i = 0
  332. }
  333. a.predefinedStartIndices[as] = i
  334. a.Unlock()
  335. }
  336. func (a *Allocator) getPredefinedPool(as string, ipV6 bool) (*net.IPNet, error) {
  337. var v ipVersion
  338. v = v4
  339. if ipV6 {
  340. v = v6
  341. }
  342. if as != localAddressSpace && as != globalAddressSpace {
  343. return nil, types.NotImplementedErrorf("no default pool available for non-default address spaces")
  344. }
  345. aSpace, err := a.getAddrSpace(as)
  346. if err != nil {
  347. return nil, err
  348. }
  349. predefined := a.getPredefineds(as)
  350. aSpace.Lock()
  351. for i, nw := range predefined {
  352. if v != getAddressVersion(nw.IP) {
  353. continue
  354. }
  355. // Checks whether pool has already been allocated
  356. if _, ok := aSpace.subnets[SubnetKey{AddressSpace: as, Subnet: nw.String()}]; ok {
  357. continue
  358. }
  359. // Shouldn't be necessary, but check prevents IP collisions should
  360. // predefined pools overlap for any reason.
  361. if !aSpace.contains(as, nw) {
  362. aSpace.Unlock()
  363. a.updateStartIndex(as, i+1)
  364. return nw, nil
  365. }
  366. }
  367. aSpace.Unlock()
  368. return nil, types.NotFoundErrorf("could not find an available, non-overlapping IPv%d address pool among the defaults to assign to the network", v)
  369. }
  370. // RequestAddress returns an address from the specified pool ID
  371. func (a *Allocator) RequestAddress(poolID string, prefAddress net.IP, opts map[string]string) (*net.IPNet, map[string]string, error) {
  372. logrus.Debugf("RequestAddress(%s, %v, %v)", poolID, prefAddress, opts)
  373. k := SubnetKey{}
  374. if err := k.FromString(poolID); err != nil {
  375. return nil, nil, types.BadRequestErrorf("invalid pool id: %s", poolID)
  376. }
  377. if err := a.refresh(k.AddressSpace); err != nil {
  378. return nil, nil, err
  379. }
  380. aSpace, err := a.getAddrSpace(k.AddressSpace)
  381. if err != nil {
  382. return nil, nil, err
  383. }
  384. aSpace.Lock()
  385. p, ok := aSpace.subnets[k]
  386. if !ok {
  387. aSpace.Unlock()
  388. return nil, nil, types.NotFoundErrorf("cannot find address pool for poolID:%s", poolID)
  389. }
  390. if prefAddress != nil && !p.Pool.Contains(prefAddress) {
  391. aSpace.Unlock()
  392. return nil, nil, ipamapi.ErrIPOutOfRange
  393. }
  394. c := p
  395. for c.Range != nil {
  396. k = c.ParentKey
  397. c = aSpace.subnets[k]
  398. }
  399. aSpace.Unlock()
  400. bm, err := a.retrieveBitmask(k, c.Pool)
  401. if err != nil {
  402. return nil, nil, types.InternalErrorf("could not find bitmask in datastore for %s on address %v request from pool %s: %v",
  403. k.String(), prefAddress, poolID, err)
  404. }
  405. // In order to request for a serial ip address allocation, callers can pass in the option to request
  406. // IP allocation serially or first available IP in the subnet
  407. var serial bool
  408. if opts != nil {
  409. if val, ok := opts[ipamapi.AllocSerialPrefix]; ok {
  410. serial = (val == "true")
  411. }
  412. }
  413. ip, err := a.getAddress(p.Pool, bm, prefAddress, p.Range, serial)
  414. if err != nil {
  415. return nil, nil, err
  416. }
  417. return &net.IPNet{IP: ip, Mask: p.Pool.Mask}, nil, nil
  418. }
  419. // ReleaseAddress releases the address from the specified pool ID
  420. func (a *Allocator) ReleaseAddress(poolID string, address net.IP) error {
  421. logrus.Debugf("ReleaseAddress(%s, %v)", poolID, address)
  422. k := SubnetKey{}
  423. if err := k.FromString(poolID); err != nil {
  424. return types.BadRequestErrorf("invalid pool id: %s", poolID)
  425. }
  426. if err := a.refresh(k.AddressSpace); err != nil {
  427. return err
  428. }
  429. aSpace, err := a.getAddrSpace(k.AddressSpace)
  430. if err != nil {
  431. return err
  432. }
  433. aSpace.Lock()
  434. p, ok := aSpace.subnets[k]
  435. if !ok {
  436. aSpace.Unlock()
  437. return types.NotFoundErrorf("cannot find address pool for poolID:%s", poolID)
  438. }
  439. if address == nil {
  440. aSpace.Unlock()
  441. return types.BadRequestErrorf("invalid address: nil")
  442. }
  443. if !p.Pool.Contains(address) {
  444. aSpace.Unlock()
  445. return ipamapi.ErrIPOutOfRange
  446. }
  447. c := p
  448. for c.Range != nil {
  449. k = c.ParentKey
  450. c = aSpace.subnets[k]
  451. }
  452. aSpace.Unlock()
  453. mask := p.Pool.Mask
  454. h, err := types.GetHostPartIP(address, mask)
  455. if err != nil {
  456. return types.InternalErrorf("failed to release address %s: %v", address.String(), err)
  457. }
  458. bm, err := a.retrieveBitmask(k, c.Pool)
  459. if err != nil {
  460. return types.InternalErrorf("could not find bitmask in datastore for %s on address %v release from pool %s: %v",
  461. k.String(), address, poolID, err)
  462. }
  463. defer logrus.Debugf("Released address PoolID:%s, Address:%v Sequence:%s", poolID, address, bm.String())
  464. return bm.Unset(ipToUint64(h))
  465. }
  466. func (a *Allocator) getAddress(nw *net.IPNet, bitmask *bitseq.Handle, prefAddress net.IP, ipr *AddressRange, serial bool) (net.IP, error) {
  467. var (
  468. ordinal uint64
  469. err error
  470. base *net.IPNet
  471. )
  472. logrus.Debugf("Request address PoolID:%v %s Serial:%v PrefAddress:%v ", nw, bitmask.String(), serial, prefAddress)
  473. base = types.GetIPNetCopy(nw)
  474. if bitmask.Unselected() == 0 {
  475. return nil, ipamapi.ErrNoAvailableIPs
  476. }
  477. if ipr == nil && prefAddress == nil {
  478. ordinal, err = bitmask.SetAny(serial)
  479. } else if prefAddress != nil {
  480. hostPart, e := types.GetHostPartIP(prefAddress, base.Mask)
  481. if e != nil {
  482. return nil, types.InternalErrorf("failed to allocate requested address %s: %v", prefAddress.String(), e)
  483. }
  484. ordinal = ipToUint64(types.GetMinimalIP(hostPart))
  485. err = bitmask.Set(ordinal)
  486. } else {
  487. ordinal, err = bitmask.SetAnyInRange(ipr.Start, ipr.End, serial)
  488. }
  489. switch err {
  490. case nil:
  491. // Convert IP ordinal for this subnet into IP address
  492. return generateAddress(ordinal, base), nil
  493. case bitseq.ErrBitAllocated:
  494. return nil, ipamapi.ErrIPAlreadyAllocated
  495. case bitseq.ErrNoBitAvailable:
  496. return nil, ipamapi.ErrNoAvailableIPs
  497. default:
  498. return nil, err
  499. }
  500. }
  501. // DumpDatabase dumps the internal info
  502. func (a *Allocator) DumpDatabase() string {
  503. a.Lock()
  504. aspaces := make(map[string]*addrSpace, len(a.addrSpaces))
  505. orderedAS := make([]string, 0, len(a.addrSpaces))
  506. for as, aSpace := range a.addrSpaces {
  507. orderedAS = append(orderedAS, as)
  508. aspaces[as] = aSpace
  509. }
  510. a.Unlock()
  511. sort.Strings(orderedAS)
  512. var s string
  513. for _, as := range orderedAS {
  514. aSpace := aspaces[as]
  515. s = fmt.Sprintf("\n\n%s Config", as)
  516. aSpace.Lock()
  517. for k, config := range aSpace.subnets {
  518. s += fmt.Sprintf("\n%v: %v", k, config)
  519. if config.Range == nil {
  520. a.retrieveBitmask(k, config.Pool)
  521. }
  522. }
  523. aSpace.Unlock()
  524. }
  525. s = fmt.Sprintf("%s\n\nBitmasks", s)
  526. for k, bm := range a.addresses {
  527. s += fmt.Sprintf("\n%s: %s", k, bm)
  528. }
  529. return s
  530. }
  531. // IsBuiltIn returns true for builtin drivers
  532. func (a *Allocator) IsBuiltIn() bool {
  533. return true
  534. }