allocator.go 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601
  1. package ipam
  2. import (
  3. "fmt"
  4. "net"
  5. "sort"
  6. "sync"
  7. "github.com/Sirupsen/logrus"
  8. "github.com/docker/libnetwork/bitseq"
  9. "github.com/docker/libnetwork/datastore"
  10. "github.com/docker/libnetwork/discoverapi"
  11. "github.com/docker/libnetwork/ipamapi"
  12. "github.com/docker/libnetwork/ipamutils"
  13. "github.com/docker/libnetwork/types"
  14. )
  15. const (
  16. localAddressSpace = "LocalDefault"
  17. globalAddressSpace = "GlobalDefault"
  18. // The biggest configurable host subnets
  19. minNetSize = 8
  20. minNetSizeV6 = 64
  21. // datastore keyes for ipam objects
  22. dsConfigKey = "ipam/" + ipamapi.DefaultIPAM + "/config"
  23. dsDataKey = "ipam/" + ipamapi.DefaultIPAM + "/data"
  24. )
  25. // Allocator provides per address space ipv4/ipv6 book keeping
  26. type Allocator struct {
  27. // Predefined pools for default address spaces
  28. predefined map[string][]*net.IPNet
  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.PredefinedBroadNetworks,
  41. globalAddressSpace: ipamutils.PredefinedGranularNetworks,
  42. }
  43. // Initialize bitseq map
  44. a.addresses = make(map[SubnetKey]*bitseq.Handle)
  45. // Initialize address spaces
  46. a.addrSpaces = make(map[string]*addrSpace)
  47. for _, aspc := range []struct {
  48. as string
  49. ds datastore.DataStore
  50. }{
  51. {localAddressSpace, lcDs},
  52. {globalAddressSpace, glDs},
  53. } {
  54. a.initializeAddressSpace(aspc.as, aspc.ds)
  55. }
  56. return a, nil
  57. }
  58. func (a *Allocator) refresh(as string) error {
  59. aSpace, err := a.getAddressSpaceFromStore(as)
  60. if err != nil {
  61. return types.InternalErrorf("error getting pools config from store: %v", err)
  62. }
  63. if aSpace == nil {
  64. return nil
  65. }
  66. a.Lock()
  67. a.addrSpaces[as] = aSpace
  68. a.Unlock()
  69. return nil
  70. }
  71. func (a *Allocator) updateBitMasks(aSpace *addrSpace) error {
  72. var inserterList []func() error
  73. aSpace.Lock()
  74. for k, v := range aSpace.subnets {
  75. if v.Range == nil {
  76. kk := k
  77. vv := v
  78. inserterList = append(inserterList, func() error { return a.insertBitMask(kk, vv.Pool) })
  79. }
  80. }
  81. aSpace.Unlock()
  82. // Add the bitmasks (data could come from datastore)
  83. if inserterList != nil {
  84. for _, f := range inserterList {
  85. if err := f(); err != nil {
  86. return err
  87. }
  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. func (a *Allocator) RequestPool(addressSpace, pool, subPool string, options map[string]string, v6 bool) (string, *net.IPNet, map[string]string, error) {
  169. logrus.Debugf("RequestPool(%s, %s, %s, %v, %t)", addressSpace, pool, subPool, options, v6)
  170. k, nw, ipr, err := a.parsePoolRequest(addressSpace, pool, subPool, v6)
  171. if err != nil {
  172. return "", nil, nil, types.InternalErrorf("failed to parse pool request for address space %q pool %q subpool %q: %v", addressSpace, pool, subPool, err)
  173. }
  174. pdf := k == nil
  175. retry:
  176. if pdf {
  177. if nw, err = a.getPredefinedPool(addressSpace, v6); err != nil {
  178. return "", nil, nil, err
  179. }
  180. k = &SubnetKey{AddressSpace: addressSpace, Subnet: nw.String()}
  181. }
  182. if err := a.refresh(addressSpace); err != nil {
  183. return "", nil, nil, err
  184. }
  185. aSpace, err := a.getAddrSpace(addressSpace)
  186. if err != nil {
  187. return "", nil, nil, err
  188. }
  189. insert, err := aSpace.updatePoolDBOnAdd(*k, nw, ipr, pdf)
  190. if err != nil {
  191. if _, ok := err.(types.MaskableError); ok {
  192. logrus.Debugf("Retrying predefined pool search: %v", err)
  193. goto retry
  194. }
  195. return "", nil, nil, err
  196. }
  197. if err := a.writeToStore(aSpace); err != nil {
  198. if _, ok := err.(types.RetryError); !ok {
  199. return "", nil, nil, types.InternalErrorf("pool configuration failed because of %s", err.Error())
  200. }
  201. goto retry
  202. }
  203. return k.String(), nw, nil, insert()
  204. }
  205. // ReleasePool releases the address pool identified by the passed id
  206. func (a *Allocator) ReleasePool(poolID string) error {
  207. logrus.Debugf("ReleasePool(%s)", poolID)
  208. k := SubnetKey{}
  209. if err := k.FromString(poolID); err != nil {
  210. return types.BadRequestErrorf("invalid pool id: %s", poolID)
  211. }
  212. retry:
  213. if err := a.refresh(k.AddressSpace); err != nil {
  214. return err
  215. }
  216. aSpace, err := a.getAddrSpace(k.AddressSpace)
  217. if err != nil {
  218. return err
  219. }
  220. remove, err := aSpace.updatePoolDBOnRemoval(k)
  221. if err != nil {
  222. return err
  223. }
  224. if err = a.writeToStore(aSpace); err != nil {
  225. if _, ok := err.(types.RetryError); !ok {
  226. return types.InternalErrorf("pool (%s) removal failed because of %v", poolID, err)
  227. }
  228. goto retry
  229. }
  230. return remove()
  231. }
  232. // Given the address space, returns the local or global PoolConfig based on the
  233. // address space is local or global. AddressSpace locality is being registered with IPAM out of band.
  234. func (a *Allocator) getAddrSpace(as string) (*addrSpace, error) {
  235. a.Lock()
  236. defer a.Unlock()
  237. aSpace, ok := a.addrSpaces[as]
  238. if !ok {
  239. return nil, types.BadRequestErrorf("cannot find address space %s (most likely the backing datastore is not configured)", as)
  240. }
  241. return aSpace, nil
  242. }
  243. func (a *Allocator) parsePoolRequest(addressSpace, pool, subPool string, v6 bool) (*SubnetKey, *net.IPNet, *AddressRange, error) {
  244. var (
  245. nw *net.IPNet
  246. ipr *AddressRange
  247. err error
  248. )
  249. if addressSpace == "" {
  250. return nil, nil, nil, ipamapi.ErrInvalidAddressSpace
  251. }
  252. if pool == "" && subPool != "" {
  253. return nil, nil, nil, ipamapi.ErrInvalidSubPool
  254. }
  255. if pool == "" {
  256. return nil, nil, nil, nil
  257. }
  258. if _, nw, err = net.ParseCIDR(pool); err != nil {
  259. return nil, nil, nil, ipamapi.ErrInvalidPool
  260. }
  261. if subPool != "" {
  262. if ipr, err = getAddressRange(subPool, nw); err != nil {
  263. return nil, nil, nil, err
  264. }
  265. }
  266. return &SubnetKey{AddressSpace: addressSpace, Subnet: nw.String(), ChildSubnet: subPool}, nw, ipr, nil
  267. }
  268. func (a *Allocator) insertBitMask(key SubnetKey, pool *net.IPNet) error {
  269. //logrus.Debugf("Inserting bitmask (%s, %s)", key.String(), pool.String())
  270. store := a.getStore(key.AddressSpace)
  271. ipVer := getAddressVersion(pool.IP)
  272. ones, bits := pool.Mask.Size()
  273. numAddresses := uint64(1 << uint(bits-ones))
  274. // Allow /64 subnet
  275. if ipVer == v6 && numAddresses == 0 {
  276. numAddresses--
  277. }
  278. // Generate the new address masks. AddressMask content may come from datastore
  279. h, err := bitseq.NewHandle(dsDataKey, store, key.String(), numAddresses)
  280. if err != nil {
  281. return err
  282. }
  283. // Do not let network identifier address be reserved
  284. // Do the same for IPv6 so that bridge ip starts with XXXX...::1
  285. h.Set(0)
  286. // Do not let broadcast address be reserved
  287. if ipVer == v4 {
  288. h.Set(numAddresses - 1)
  289. }
  290. a.Lock()
  291. a.addresses[key] = h
  292. a.Unlock()
  293. return nil
  294. }
  295. func (a *Allocator) retrieveBitmask(k SubnetKey, n *net.IPNet) (*bitseq.Handle, error) {
  296. a.Lock()
  297. bm, ok := a.addresses[k]
  298. a.Unlock()
  299. if !ok {
  300. logrus.Debugf("Retrieving bitmask (%s, %s)", k.String(), n.String())
  301. if err := a.insertBitMask(k, n); err != nil {
  302. return nil, types.InternalErrorf("could not find bitmask in datastore for %s", k.String())
  303. }
  304. a.Lock()
  305. bm = a.addresses[k]
  306. a.Unlock()
  307. }
  308. return bm, nil
  309. }
  310. func (a *Allocator) getPredefineds(as string) []*net.IPNet {
  311. a.Lock()
  312. defer a.Unlock()
  313. l := make([]*net.IPNet, 0, len(a.predefined[as]))
  314. for _, pool := range a.predefined[as] {
  315. l = append(l, pool)
  316. }
  317. return l
  318. }
  319. func (a *Allocator) getPredefinedPool(as string, ipV6 bool) (*net.IPNet, error) {
  320. var v ipVersion
  321. v = v4
  322. if ipV6 {
  323. v = v6
  324. }
  325. if as != localAddressSpace && as != globalAddressSpace {
  326. return nil, types.NotImplementedErrorf("no default pool availbale for non-default addresss spaces")
  327. }
  328. aSpace, err := a.getAddrSpace(as)
  329. if err != nil {
  330. return nil, err
  331. }
  332. for _, nw := range a.getPredefineds(as) {
  333. if v != getAddressVersion(nw.IP) {
  334. continue
  335. }
  336. aSpace.Lock()
  337. _, ok := aSpace.subnets[SubnetKey{AddressSpace: as, Subnet: nw.String()}]
  338. aSpace.Unlock()
  339. if ok {
  340. continue
  341. }
  342. if !aSpace.contains(as, nw) {
  343. return nw, nil
  344. }
  345. }
  346. return nil, types.NotFoundErrorf("could not find an available, non-overlapping IPv%d address pool among the defaults to assign to the network", v)
  347. }
  348. // RequestAddress returns an address from the specified pool ID
  349. func (a *Allocator) RequestAddress(poolID string, prefAddress net.IP, opts map[string]string) (*net.IPNet, map[string]string, error) {
  350. logrus.Debugf("RequestAddress(%s, %v, %v)", poolID, prefAddress, opts)
  351. k := SubnetKey{}
  352. if err := k.FromString(poolID); err != nil {
  353. return nil, nil, types.BadRequestErrorf("invalid pool id: %s", poolID)
  354. }
  355. if err := a.refresh(k.AddressSpace); err != nil {
  356. return nil, nil, err
  357. }
  358. aSpace, err := a.getAddrSpace(k.AddressSpace)
  359. if err != nil {
  360. return nil, nil, err
  361. }
  362. aSpace.Lock()
  363. p, ok := aSpace.subnets[k]
  364. if !ok {
  365. aSpace.Unlock()
  366. return nil, nil, types.NotFoundErrorf("cannot find address pool for poolID:%s", poolID)
  367. }
  368. if prefAddress != nil && !p.Pool.Contains(prefAddress) {
  369. aSpace.Unlock()
  370. return nil, nil, ipamapi.ErrIPOutOfRange
  371. }
  372. c := p
  373. for c.Range != nil {
  374. k = c.ParentKey
  375. c, ok = aSpace.subnets[k]
  376. }
  377. aSpace.Unlock()
  378. bm, err := a.retrieveBitmask(k, c.Pool)
  379. if err != nil {
  380. return nil, nil, types.InternalErrorf("could not find bitmask in datastore for %s on address %v request from pool %s: %v",
  381. k.String(), prefAddress, poolID, err)
  382. }
  383. ip, err := a.getAddress(p.Pool, bm, prefAddress, p.Range)
  384. if err != nil {
  385. return nil, nil, err
  386. }
  387. return &net.IPNet{IP: ip, Mask: p.Pool.Mask}, nil, nil
  388. }
  389. // ReleaseAddress releases the address from the specified pool ID
  390. func (a *Allocator) ReleaseAddress(poolID string, address net.IP) error {
  391. logrus.Debugf("ReleaseAddress(%s, %v)", poolID, address)
  392. k := SubnetKey{}
  393. if err := k.FromString(poolID); err != nil {
  394. return types.BadRequestErrorf("invalid pool id: %s", poolID)
  395. }
  396. if err := a.refresh(k.AddressSpace); err != nil {
  397. return err
  398. }
  399. aSpace, err := a.getAddrSpace(k.AddressSpace)
  400. if err != nil {
  401. return err
  402. }
  403. aSpace.Lock()
  404. p, ok := aSpace.subnets[k]
  405. if !ok {
  406. aSpace.Unlock()
  407. return types.NotFoundErrorf("cannot find address pool for poolID:%s", poolID)
  408. }
  409. if address == nil {
  410. aSpace.Unlock()
  411. return types.BadRequestErrorf("invalid address: nil")
  412. }
  413. if !p.Pool.Contains(address) {
  414. aSpace.Unlock()
  415. return ipamapi.ErrIPOutOfRange
  416. }
  417. c := p
  418. for c.Range != nil {
  419. k = c.ParentKey
  420. c = aSpace.subnets[k]
  421. }
  422. aSpace.Unlock()
  423. mask := p.Pool.Mask
  424. h, err := types.GetHostPartIP(address, mask)
  425. if err != nil {
  426. return types.InternalErrorf("failed to release address %s: %v", address.String(), err)
  427. }
  428. bm, err := a.retrieveBitmask(k, c.Pool)
  429. if err != nil {
  430. return types.InternalErrorf("could not find bitmask in datastore for %s on address %v release from pool %s: %v",
  431. k.String(), address, poolID, err)
  432. }
  433. return bm.Unset(ipToUint64(h))
  434. }
  435. func (a *Allocator) getAddress(nw *net.IPNet, bitmask *bitseq.Handle, prefAddress net.IP, ipr *AddressRange) (net.IP, error) {
  436. var (
  437. ordinal uint64
  438. err error
  439. base *net.IPNet
  440. )
  441. base = types.GetIPNetCopy(nw)
  442. if bitmask.Unselected() <= 0 {
  443. return nil, ipamapi.ErrNoAvailableIPs
  444. }
  445. if ipr == nil && prefAddress == nil {
  446. ordinal, err = bitmask.SetAny()
  447. } else if prefAddress != nil {
  448. hostPart, e := types.GetHostPartIP(prefAddress, base.Mask)
  449. if e != nil {
  450. return nil, types.InternalErrorf("failed to allocate requested address %s: %v", prefAddress.String(), e)
  451. }
  452. ordinal = ipToUint64(types.GetMinimalIP(hostPart))
  453. err = bitmask.Set(ordinal)
  454. } else {
  455. ordinal, err = bitmask.SetAnyInRange(ipr.Start, ipr.End)
  456. }
  457. switch err {
  458. case nil:
  459. // Convert IP ordinal for this subnet into IP address
  460. return generateAddress(ordinal, base), nil
  461. case bitseq.ErrBitAllocated:
  462. return nil, ipamapi.ErrIPAlreadyAllocated
  463. case bitseq.ErrNoBitAvailable:
  464. return nil, ipamapi.ErrNoAvailableIPs
  465. default:
  466. return nil, err
  467. }
  468. }
  469. // DumpDatabase dumps the internal info
  470. func (a *Allocator) DumpDatabase() string {
  471. a.Lock()
  472. aspaces := make(map[string]*addrSpace, len(a.addrSpaces))
  473. orderedAS := make([]string, 0, len(a.addrSpaces))
  474. for as, aSpace := range a.addrSpaces {
  475. orderedAS = append(orderedAS, as)
  476. aspaces[as] = aSpace
  477. }
  478. a.Unlock()
  479. sort.Strings(orderedAS)
  480. var s string
  481. for _, as := range orderedAS {
  482. aSpace := aspaces[as]
  483. s = fmt.Sprintf("\n\n%s Config", as)
  484. aSpace.Lock()
  485. for k, config := range aSpace.subnets {
  486. s = fmt.Sprintf("%s%s", s, fmt.Sprintf("\n%v: %v", k, config))
  487. if config.Range == nil {
  488. a.retrieveBitmask(k, config.Pool)
  489. }
  490. }
  491. aSpace.Unlock()
  492. }
  493. s = fmt.Sprintf("%s\n\nBitmasks", s)
  494. for k, bm := range a.addresses {
  495. s = fmt.Sprintf("%s%s", s, fmt.Sprintf("\n%s: %s", k, bm))
  496. }
  497. return s
  498. }
  499. // IsBuiltIn returns true for builtin drivers
  500. func (a *Allocator) IsBuiltIn() bool {
  501. return true
  502. }