[VOL-4291] Rw-core updates for gRPC migration
Change-Id: I8d5a554409115b29318089671ca4e1ab3fa98810
diff --git a/vendor/github.com/coreos/etcd/store/doc.go b/vendor/github.com/coreos/etcd/store/doc.go
new file mode 100644
index 0000000..612df92
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/doc.go
@@ -0,0 +1,16 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Package store defines etcd's in-memory key/value store.
+package store
diff --git a/vendor/github.com/coreos/etcd/store/event.go b/vendor/github.com/coreos/etcd/store/event.go
new file mode 100644
index 0000000..efcddb0
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/event.go
@@ -0,0 +1,71 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+const (
+ Get = "get"
+ Create = "create"
+ Set = "set"
+ Update = "update"
+ Delete = "delete"
+ CompareAndSwap = "compareAndSwap"
+ CompareAndDelete = "compareAndDelete"
+ Expire = "expire"
+)
+
+type Event struct {
+ Action string `json:"action"`
+ Node *NodeExtern `json:"node,omitempty"`
+ PrevNode *NodeExtern `json:"prevNode,omitempty"`
+ EtcdIndex uint64 `json:"-"`
+ Refresh bool `json:"refresh,omitempty"`
+}
+
+func newEvent(action string, key string, modifiedIndex, createdIndex uint64) *Event {
+ n := &NodeExtern{
+ Key: key,
+ ModifiedIndex: modifiedIndex,
+ CreatedIndex: createdIndex,
+ }
+
+ return &Event{
+ Action: action,
+ Node: n,
+ }
+}
+
+func (e *Event) IsCreated() bool {
+ if e.Action == Create {
+ return true
+ }
+ return e.Action == Set && e.PrevNode == nil
+}
+
+func (e *Event) Index() uint64 {
+ return e.Node.ModifiedIndex
+}
+
+func (e *Event) Clone() *Event {
+ return &Event{
+ Action: e.Action,
+ EtcdIndex: e.EtcdIndex,
+ Node: e.Node.Clone(),
+ PrevNode: e.PrevNode.Clone(),
+ }
+}
+
+func (e *Event) SetRefresh() {
+ e.Refresh = true
+}
diff --git a/vendor/github.com/coreos/etcd/store/event_history.go b/vendor/github.com/coreos/etcd/store/event_history.go
new file mode 100644
index 0000000..235d87a
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/event_history.go
@@ -0,0 +1,129 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "fmt"
+ "path"
+ "strings"
+ "sync"
+
+ etcdErr "github.com/coreos/etcd/error"
+)
+
+type EventHistory struct {
+ Queue eventQueue
+ StartIndex uint64
+ LastIndex uint64
+ rwl sync.RWMutex
+}
+
+func newEventHistory(capacity int) *EventHistory {
+ return &EventHistory{
+ Queue: eventQueue{
+ Capacity: capacity,
+ Events: make([]*Event, capacity),
+ },
+ }
+}
+
+// addEvent function adds event into the eventHistory
+func (eh *EventHistory) addEvent(e *Event) *Event {
+ eh.rwl.Lock()
+ defer eh.rwl.Unlock()
+
+ eh.Queue.insert(e)
+
+ eh.LastIndex = e.Index()
+
+ eh.StartIndex = eh.Queue.Events[eh.Queue.Front].Index()
+
+ return e
+}
+
+// scan enumerates events from the index history and stops at the first point
+// where the key matches.
+func (eh *EventHistory) scan(key string, recursive bool, index uint64) (*Event, *etcdErr.Error) {
+ eh.rwl.RLock()
+ defer eh.rwl.RUnlock()
+
+ // index should be after the event history's StartIndex
+ if index < eh.StartIndex {
+ return nil,
+ etcdErr.NewError(etcdErr.EcodeEventIndexCleared,
+ fmt.Sprintf("the requested history has been cleared [%v/%v]",
+ eh.StartIndex, index), 0)
+ }
+
+ // the index should come before the size of the queue minus the duplicate count
+ if index > eh.LastIndex { // future index
+ return nil, nil
+ }
+
+ offset := index - eh.StartIndex
+ i := (eh.Queue.Front + int(offset)) % eh.Queue.Capacity
+
+ for {
+ e := eh.Queue.Events[i]
+
+ if !e.Refresh {
+ ok := (e.Node.Key == key)
+
+ if recursive {
+ // add tailing slash
+ nkey := path.Clean(key)
+ if nkey[len(nkey)-1] != '/' {
+ nkey = nkey + "/"
+ }
+
+ ok = ok || strings.HasPrefix(e.Node.Key, nkey)
+ }
+
+ if (e.Action == Delete || e.Action == Expire) && e.PrevNode != nil && e.PrevNode.Dir {
+ ok = ok || strings.HasPrefix(key, e.PrevNode.Key)
+ }
+
+ if ok {
+ return e, nil
+ }
+ }
+
+ i = (i + 1) % eh.Queue.Capacity
+
+ if i == eh.Queue.Back {
+ return nil, nil
+ }
+ }
+}
+
+// clone will be protected by a stop-world lock
+// do not need to obtain internal lock
+func (eh *EventHistory) clone() *EventHistory {
+ clonedQueue := eventQueue{
+ Capacity: eh.Queue.Capacity,
+ Events: make([]*Event, eh.Queue.Capacity),
+ Size: eh.Queue.Size,
+ Front: eh.Queue.Front,
+ Back: eh.Queue.Back,
+ }
+
+ copy(clonedQueue.Events, eh.Queue.Events)
+ return &EventHistory{
+ StartIndex: eh.StartIndex,
+ Queue: clonedQueue,
+ LastIndex: eh.LastIndex,
+ }
+
+}
diff --git a/vendor/github.com/coreos/etcd/store/event_queue.go b/vendor/github.com/coreos/etcd/store/event_queue.go
new file mode 100644
index 0000000..767b835
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/event_queue.go
@@ -0,0 +1,34 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+type eventQueue struct {
+ Events []*Event
+ Size int
+ Front int
+ Back int
+ Capacity int
+}
+
+func (eq *eventQueue) insert(e *Event) {
+ eq.Events[eq.Back] = e
+ eq.Back = (eq.Back + 1) % eq.Capacity
+
+ if eq.Size == eq.Capacity { //dequeue
+ eq.Front = (eq.Front + 1) % eq.Capacity
+ } else {
+ eq.Size++
+ }
+}
diff --git a/vendor/github.com/coreos/etcd/store/metrics.go b/vendor/github.com/coreos/etcd/store/metrics.go
new file mode 100644
index 0000000..077c0fa
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/metrics.go
@@ -0,0 +1,132 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "github.com/prometheus/client_golang/prometheus"
+)
+
+// Set of raw Prometheus metrics.
+// Labels
+// * action = declared in event.go
+// * outcome = Outcome
+// Do not increment directly, use Report* methods.
+var (
+ readCounter = prometheus.NewCounterVec(
+ prometheus.CounterOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "reads_total",
+ Help: "Total number of reads action by (get/getRecursive), local to this member.",
+ }, []string{"action"})
+
+ writeCounter = prometheus.NewCounterVec(
+ prometheus.CounterOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "writes_total",
+ Help: "Total number of writes (e.g. set/compareAndDelete) seen by this member.",
+ }, []string{"action"})
+
+ readFailedCounter = prometheus.NewCounterVec(
+ prometheus.CounterOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "reads_failed_total",
+ Help: "Failed read actions by (get/getRecursive), local to this member.",
+ }, []string{"action"})
+
+ writeFailedCounter = prometheus.NewCounterVec(
+ prometheus.CounterOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "writes_failed_total",
+ Help: "Failed write actions (e.g. set/compareAndDelete), seen by this member.",
+ }, []string{"action"})
+
+ expireCounter = prometheus.NewCounter(
+ prometheus.CounterOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "expires_total",
+ Help: "Total number of expired keys.",
+ })
+
+ watchRequests = prometheus.NewCounter(
+ prometheus.CounterOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "watch_requests_total",
+ Help: "Total number of incoming watch requests (new or reestablished).",
+ })
+
+ watcherCount = prometheus.NewGauge(
+ prometheus.GaugeOpts{
+ Namespace: "etcd_debugging",
+ Subsystem: "store",
+ Name: "watchers",
+ Help: "Count of currently active watchers.",
+ })
+)
+
+const (
+ GetRecursive = "getRecursive"
+)
+
+func init() {
+ if prometheus.Register(readCounter) != nil {
+ // Tests will try to double register since the tests use both
+ // store and store_test packages; ignore second attempts.
+ return
+ }
+ prometheus.MustRegister(writeCounter)
+ prometheus.MustRegister(expireCounter)
+ prometheus.MustRegister(watchRequests)
+ prometheus.MustRegister(watcherCount)
+}
+
+func reportReadSuccess(read_action string) {
+ readCounter.WithLabelValues(read_action).Inc()
+}
+
+func reportReadFailure(read_action string) {
+ readCounter.WithLabelValues(read_action).Inc()
+ readFailedCounter.WithLabelValues(read_action).Inc()
+}
+
+func reportWriteSuccess(write_action string) {
+ writeCounter.WithLabelValues(write_action).Inc()
+}
+
+func reportWriteFailure(write_action string) {
+ writeCounter.WithLabelValues(write_action).Inc()
+ writeFailedCounter.WithLabelValues(write_action).Inc()
+}
+
+func reportExpiredKey() {
+ expireCounter.Inc()
+}
+
+func reportWatchRequest() {
+ watchRequests.Inc()
+}
+
+func reportWatcherAdded() {
+ watcherCount.Inc()
+}
+
+func reportWatcherRemoved() {
+ watcherCount.Dec()
+}
diff --git a/vendor/github.com/coreos/etcd/store/node.go b/vendor/github.com/coreos/etcd/store/node.go
new file mode 100644
index 0000000..c3c8743
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/node.go
@@ -0,0 +1,395 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "path"
+ "sort"
+ "time"
+
+ etcdErr "github.com/coreos/etcd/error"
+ "github.com/jonboulle/clockwork"
+)
+
+// explanations of Compare function result
+const (
+ CompareMatch = iota
+ CompareIndexNotMatch
+ CompareValueNotMatch
+ CompareNotMatch
+)
+
+var Permanent time.Time
+
+// node is the basic element in the store system.
+// A key-value pair will have a string value
+// A directory will have a children map
+type node struct {
+ Path string
+
+ CreatedIndex uint64
+ ModifiedIndex uint64
+
+ Parent *node `json:"-"` // should not encode this field! avoid circular dependency.
+
+ ExpireTime time.Time
+ Value string // for key-value pair
+ Children map[string]*node // for directory
+
+ // A reference to the store this node is attached to.
+ store *store
+}
+
+// newKV creates a Key-Value pair
+func newKV(store *store, nodePath string, value string, createdIndex uint64, parent *node, expireTime time.Time) *node {
+ return &node{
+ Path: nodePath,
+ CreatedIndex: createdIndex,
+ ModifiedIndex: createdIndex,
+ Parent: parent,
+ store: store,
+ ExpireTime: expireTime,
+ Value: value,
+ }
+}
+
+// newDir creates a directory
+func newDir(store *store, nodePath string, createdIndex uint64, parent *node, expireTime time.Time) *node {
+ return &node{
+ Path: nodePath,
+ CreatedIndex: createdIndex,
+ ModifiedIndex: createdIndex,
+ Parent: parent,
+ ExpireTime: expireTime,
+ Children: make(map[string]*node),
+ store: store,
+ }
+}
+
+// IsHidden function checks if the node is a hidden node. A hidden node
+// will begin with '_'
+// A hidden node will not be shown via get command under a directory
+// For example if we have /foo/_hidden and /foo/notHidden, get "/foo"
+// will only return /foo/notHidden
+func (n *node) IsHidden() bool {
+ _, name := path.Split(n.Path)
+
+ return name[0] == '_'
+}
+
+// IsPermanent function checks if the node is a permanent one.
+func (n *node) IsPermanent() bool {
+ // we use a uninitialized time.Time to indicate the node is a
+ // permanent one.
+ // the uninitialized time.Time should equal zero.
+ return n.ExpireTime.IsZero()
+}
+
+// IsDir function checks whether the node is a directory.
+// If the node is a directory, the function will return true.
+// Otherwise the function will return false.
+func (n *node) IsDir() bool {
+ return n.Children != nil
+}
+
+// Read function gets the value of the node.
+// If the receiver node is not a key-value pair, a "Not A File" error will be returned.
+func (n *node) Read() (string, *etcdErr.Error) {
+ if n.IsDir() {
+ return "", etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.CurrentIndex)
+ }
+
+ return n.Value, nil
+}
+
+// Write function set the value of the node to the given value.
+// If the receiver node is a directory, a "Not A File" error will be returned.
+func (n *node) Write(value string, index uint64) *etcdErr.Error {
+ if n.IsDir() {
+ return etcdErr.NewError(etcdErr.EcodeNotFile, "", n.store.CurrentIndex)
+ }
+
+ n.Value = value
+ n.ModifiedIndex = index
+
+ return nil
+}
+
+func (n *node) expirationAndTTL(clock clockwork.Clock) (*time.Time, int64) {
+ if !n.IsPermanent() {
+ /* compute ttl as:
+ ceiling( (expireTime - timeNow) / nanosecondsPerSecond )
+ which ranges from 1..n
+ rather than as:
+ ( (expireTime - timeNow) / nanosecondsPerSecond ) + 1
+ which ranges 1..n+1
+ */
+ ttlN := n.ExpireTime.Sub(clock.Now())
+ ttl := ttlN / time.Second
+ if (ttlN % time.Second) > 0 {
+ ttl++
+ }
+ t := n.ExpireTime.UTC()
+ return &t, int64(ttl)
+ }
+ return nil, 0
+}
+
+// List function return a slice of nodes under the receiver node.
+// If the receiver node is not a directory, a "Not A Directory" error will be returned.
+func (n *node) List() ([]*node, *etcdErr.Error) {
+ if !n.IsDir() {
+ return nil, etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.CurrentIndex)
+ }
+
+ nodes := make([]*node, len(n.Children))
+
+ i := 0
+ for _, node := range n.Children {
+ nodes[i] = node
+ i++
+ }
+
+ return nodes, nil
+}
+
+// GetChild function returns the child node under the directory node.
+// On success, it returns the file node
+func (n *node) GetChild(name string) (*node, *etcdErr.Error) {
+ if !n.IsDir() {
+ return nil, etcdErr.NewError(etcdErr.EcodeNotDir, n.Path, n.store.CurrentIndex)
+ }
+
+ child, ok := n.Children[name]
+
+ if ok {
+ return child, nil
+ }
+
+ return nil, nil
+}
+
+// Add function adds a node to the receiver node.
+// If the receiver is not a directory, a "Not A Directory" error will be returned.
+// If there is an existing node with the same name under the directory, a "Already Exist"
+// error will be returned
+func (n *node) Add(child *node) *etcdErr.Error {
+ if !n.IsDir() {
+ return etcdErr.NewError(etcdErr.EcodeNotDir, "", n.store.CurrentIndex)
+ }
+
+ _, name := path.Split(child.Path)
+
+ if _, ok := n.Children[name]; ok {
+ return etcdErr.NewError(etcdErr.EcodeNodeExist, "", n.store.CurrentIndex)
+ }
+
+ n.Children[name] = child
+
+ return nil
+}
+
+// Remove function remove the node.
+func (n *node) Remove(dir, recursive bool, callback func(path string)) *etcdErr.Error {
+ if !n.IsDir() { // key-value pair
+ _, name := path.Split(n.Path)
+
+ // find its parent and remove the node from the map
+ if n.Parent != nil && n.Parent.Children[name] == n {
+ delete(n.Parent.Children, name)
+ }
+
+ if callback != nil {
+ callback(n.Path)
+ }
+
+ if !n.IsPermanent() {
+ n.store.ttlKeyHeap.remove(n)
+ }
+
+ return nil
+ }
+
+ if !dir {
+ // cannot delete a directory without dir set to true
+ return etcdErr.NewError(etcdErr.EcodeNotFile, n.Path, n.store.CurrentIndex)
+ }
+
+ if len(n.Children) != 0 && !recursive {
+ // cannot delete a directory if it is not empty and the operation
+ // is not recursive
+ return etcdErr.NewError(etcdErr.EcodeDirNotEmpty, n.Path, n.store.CurrentIndex)
+ }
+
+ for _, child := range n.Children { // delete all children
+ child.Remove(true, true, callback)
+ }
+
+ // delete self
+ _, name := path.Split(n.Path)
+ if n.Parent != nil && n.Parent.Children[name] == n {
+ delete(n.Parent.Children, name)
+
+ if callback != nil {
+ callback(n.Path)
+ }
+
+ if !n.IsPermanent() {
+ n.store.ttlKeyHeap.remove(n)
+ }
+ }
+
+ return nil
+}
+
+func (n *node) Repr(recursive, sorted bool, clock clockwork.Clock) *NodeExtern {
+ if n.IsDir() {
+ node := &NodeExtern{
+ Key: n.Path,
+ Dir: true,
+ ModifiedIndex: n.ModifiedIndex,
+ CreatedIndex: n.CreatedIndex,
+ }
+ node.Expiration, node.TTL = n.expirationAndTTL(clock)
+
+ if !recursive {
+ return node
+ }
+
+ children, _ := n.List()
+ node.Nodes = make(NodeExterns, len(children))
+
+ // we do not use the index in the children slice directly
+ // we need to skip the hidden one
+ i := 0
+
+ for _, child := range children {
+
+ if child.IsHidden() { // get will not list hidden node
+ continue
+ }
+
+ node.Nodes[i] = child.Repr(recursive, sorted, clock)
+
+ i++
+ }
+
+ // eliminate hidden nodes
+ node.Nodes = node.Nodes[:i]
+ if sorted {
+ sort.Sort(node.Nodes)
+ }
+
+ return node
+ }
+
+ // since n.Value could be changed later, so we need to copy the value out
+ value := n.Value
+ node := &NodeExtern{
+ Key: n.Path,
+ Value: &value,
+ ModifiedIndex: n.ModifiedIndex,
+ CreatedIndex: n.CreatedIndex,
+ }
+ node.Expiration, node.TTL = n.expirationAndTTL(clock)
+ return node
+}
+
+func (n *node) UpdateTTL(expireTime time.Time) {
+ if !n.IsPermanent() {
+ if expireTime.IsZero() {
+ // from ttl to permanent
+ n.ExpireTime = expireTime
+ // remove from ttl heap
+ n.store.ttlKeyHeap.remove(n)
+ return
+ }
+
+ // update ttl
+ n.ExpireTime = expireTime
+ // update ttl heap
+ n.store.ttlKeyHeap.update(n)
+ return
+ }
+
+ if expireTime.IsZero() {
+ return
+ }
+
+ // from permanent to ttl
+ n.ExpireTime = expireTime
+ // push into ttl heap
+ n.store.ttlKeyHeap.push(n)
+}
+
+// Compare function compares node index and value with provided ones.
+// second result value explains result and equals to one of Compare.. constants
+func (n *node) Compare(prevValue string, prevIndex uint64) (ok bool, which int) {
+ indexMatch := (prevIndex == 0 || n.ModifiedIndex == prevIndex)
+ valueMatch := (prevValue == "" || n.Value == prevValue)
+ ok = valueMatch && indexMatch
+ switch {
+ case valueMatch && indexMatch:
+ which = CompareMatch
+ case indexMatch && !valueMatch:
+ which = CompareValueNotMatch
+ case valueMatch && !indexMatch:
+ which = CompareIndexNotMatch
+ default:
+ which = CompareNotMatch
+ }
+ return ok, which
+}
+
+// Clone function clone the node recursively and return the new node.
+// If the node is a directory, it will clone all the content under this directory.
+// If the node is a key-value pair, it will clone the pair.
+func (n *node) Clone() *node {
+ if !n.IsDir() {
+ newkv := newKV(n.store, n.Path, n.Value, n.CreatedIndex, n.Parent, n.ExpireTime)
+ newkv.ModifiedIndex = n.ModifiedIndex
+ return newkv
+ }
+
+ clone := newDir(n.store, n.Path, n.CreatedIndex, n.Parent, n.ExpireTime)
+ clone.ModifiedIndex = n.ModifiedIndex
+
+ for key, child := range n.Children {
+ clone.Children[key] = child.Clone()
+ }
+
+ return clone
+}
+
+// recoverAndclean function help to do recovery.
+// Two things need to be done: 1. recovery structure; 2. delete expired nodes
+//
+// If the node is a directory, it will help recover children's parent pointer and recursively
+// call this function on its children.
+// We check the expire last since we need to recover the whole structure first and add all the
+// notifications into the event history.
+func (n *node) recoverAndclean() {
+ if n.IsDir() {
+ for _, child := range n.Children {
+ child.Parent = n
+ child.store = n.store
+ child.recoverAndclean()
+ }
+ }
+
+ if !n.ExpireTime.IsZero() {
+ n.store.ttlKeyHeap.push(n)
+ }
+}
diff --git a/vendor/github.com/coreos/etcd/store/node_extern.go b/vendor/github.com/coreos/etcd/store/node_extern.go
new file mode 100644
index 0000000..7ba870c
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/node_extern.go
@@ -0,0 +1,116 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "sort"
+ "time"
+
+ "github.com/jonboulle/clockwork"
+)
+
+// NodeExtern is the external representation of the
+// internal node with additional fields
+// PrevValue is the previous value of the node
+// TTL is time to live in second
+type NodeExtern struct {
+ Key string `json:"key,omitempty"`
+ Value *string `json:"value,omitempty"`
+ Dir bool `json:"dir,omitempty"`
+ Expiration *time.Time `json:"expiration,omitempty"`
+ TTL int64 `json:"ttl,omitempty"`
+ Nodes NodeExterns `json:"nodes,omitempty"`
+ ModifiedIndex uint64 `json:"modifiedIndex,omitempty"`
+ CreatedIndex uint64 `json:"createdIndex,omitempty"`
+}
+
+func (eNode *NodeExtern) loadInternalNode(n *node, recursive, sorted bool, clock clockwork.Clock) {
+ if n.IsDir() { // node is a directory
+ eNode.Dir = true
+
+ children, _ := n.List()
+ eNode.Nodes = make(NodeExterns, len(children))
+
+ // we do not use the index in the children slice directly
+ // we need to skip the hidden one
+ i := 0
+
+ for _, child := range children {
+ if child.IsHidden() { // get will not return hidden nodes
+ continue
+ }
+
+ eNode.Nodes[i] = child.Repr(recursive, sorted, clock)
+ i++
+ }
+
+ // eliminate hidden nodes
+ eNode.Nodes = eNode.Nodes[:i]
+
+ if sorted {
+ sort.Sort(eNode.Nodes)
+ }
+
+ } else { // node is a file
+ value, _ := n.Read()
+ eNode.Value = &value
+ }
+
+ eNode.Expiration, eNode.TTL = n.expirationAndTTL(clock)
+}
+
+func (eNode *NodeExtern) Clone() *NodeExtern {
+ if eNode == nil {
+ return nil
+ }
+ nn := &NodeExtern{
+ Key: eNode.Key,
+ Dir: eNode.Dir,
+ TTL: eNode.TTL,
+ ModifiedIndex: eNode.ModifiedIndex,
+ CreatedIndex: eNode.CreatedIndex,
+ }
+ if eNode.Value != nil {
+ s := *eNode.Value
+ nn.Value = &s
+ }
+ if eNode.Expiration != nil {
+ t := *eNode.Expiration
+ nn.Expiration = &t
+ }
+ if eNode.Nodes != nil {
+ nn.Nodes = make(NodeExterns, len(eNode.Nodes))
+ for i, n := range eNode.Nodes {
+ nn.Nodes[i] = n.Clone()
+ }
+ }
+ return nn
+}
+
+type NodeExterns []*NodeExtern
+
+// interfaces for sorting
+
+func (ns NodeExterns) Len() int {
+ return len(ns)
+}
+
+func (ns NodeExterns) Less(i, j int) bool {
+ return ns[i].Key < ns[j].Key
+}
+
+func (ns NodeExterns) Swap(i, j int) {
+ ns[i], ns[j] = ns[j], ns[i]
+}
diff --git a/vendor/github.com/coreos/etcd/store/stats.go b/vendor/github.com/coreos/etcd/store/stats.go
new file mode 100644
index 0000000..ce464dd
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/stats.go
@@ -0,0 +1,145 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "encoding/json"
+ "sync/atomic"
+)
+
+const (
+ SetSuccess = iota
+ SetFail
+ DeleteSuccess
+ DeleteFail
+ CreateSuccess
+ CreateFail
+ UpdateSuccess
+ UpdateFail
+ CompareAndSwapSuccess
+ CompareAndSwapFail
+ GetSuccess
+ GetFail
+ ExpireCount
+ CompareAndDeleteSuccess
+ CompareAndDeleteFail
+)
+
+type Stats struct {
+ // Number of get requests
+
+ GetSuccess uint64 `json:"getsSuccess"`
+ GetFail uint64 `json:"getsFail"`
+
+ // Number of sets requests
+
+ SetSuccess uint64 `json:"setsSuccess"`
+ SetFail uint64 `json:"setsFail"`
+
+ // Number of delete requests
+
+ DeleteSuccess uint64 `json:"deleteSuccess"`
+ DeleteFail uint64 `json:"deleteFail"`
+
+ // Number of update requests
+
+ UpdateSuccess uint64 `json:"updateSuccess"`
+ UpdateFail uint64 `json:"updateFail"`
+
+ // Number of create requests
+
+ CreateSuccess uint64 `json:"createSuccess"`
+ CreateFail uint64 `json:"createFail"`
+
+ // Number of testAndSet requests
+
+ CompareAndSwapSuccess uint64 `json:"compareAndSwapSuccess"`
+ CompareAndSwapFail uint64 `json:"compareAndSwapFail"`
+
+ // Number of compareAndDelete requests
+
+ CompareAndDeleteSuccess uint64 `json:"compareAndDeleteSuccess"`
+ CompareAndDeleteFail uint64 `json:"compareAndDeleteFail"`
+
+ ExpireCount uint64 `json:"expireCount"`
+
+ Watchers uint64 `json:"watchers"`
+}
+
+func newStats() *Stats {
+ s := new(Stats)
+ return s
+}
+
+func (s *Stats) clone() *Stats {
+ return &Stats{
+ GetSuccess: s.GetSuccess,
+ GetFail: s.GetFail,
+ SetSuccess: s.SetSuccess,
+ SetFail: s.SetFail,
+ DeleteSuccess: s.DeleteSuccess,
+ DeleteFail: s.DeleteFail,
+ UpdateSuccess: s.UpdateSuccess,
+ UpdateFail: s.UpdateFail,
+ CreateSuccess: s.CreateSuccess,
+ CreateFail: s.CreateFail,
+ CompareAndSwapSuccess: s.CompareAndSwapSuccess,
+ CompareAndSwapFail: s.CompareAndSwapFail,
+ CompareAndDeleteSuccess: s.CompareAndDeleteSuccess,
+ CompareAndDeleteFail: s.CompareAndDeleteFail,
+ ExpireCount: s.ExpireCount,
+ Watchers: s.Watchers,
+ }
+}
+
+func (s *Stats) toJson() []byte {
+ b, _ := json.Marshal(s)
+ return b
+}
+
+func (s *Stats) Inc(field int) {
+ switch field {
+ case SetSuccess:
+ atomic.AddUint64(&s.SetSuccess, 1)
+ case SetFail:
+ atomic.AddUint64(&s.SetFail, 1)
+ case CreateSuccess:
+ atomic.AddUint64(&s.CreateSuccess, 1)
+ case CreateFail:
+ atomic.AddUint64(&s.CreateFail, 1)
+ case DeleteSuccess:
+ atomic.AddUint64(&s.DeleteSuccess, 1)
+ case DeleteFail:
+ atomic.AddUint64(&s.DeleteFail, 1)
+ case GetSuccess:
+ atomic.AddUint64(&s.GetSuccess, 1)
+ case GetFail:
+ atomic.AddUint64(&s.GetFail, 1)
+ case UpdateSuccess:
+ atomic.AddUint64(&s.UpdateSuccess, 1)
+ case UpdateFail:
+ atomic.AddUint64(&s.UpdateFail, 1)
+ case CompareAndSwapSuccess:
+ atomic.AddUint64(&s.CompareAndSwapSuccess, 1)
+ case CompareAndSwapFail:
+ atomic.AddUint64(&s.CompareAndSwapFail, 1)
+ case CompareAndDeleteSuccess:
+ atomic.AddUint64(&s.CompareAndDeleteSuccess, 1)
+ case CompareAndDeleteFail:
+ atomic.AddUint64(&s.CompareAndDeleteFail, 1)
+ case ExpireCount:
+ atomic.AddUint64(&s.ExpireCount, 1)
+ }
+}
diff --git a/vendor/github.com/coreos/etcd/store/store.go b/vendor/github.com/coreos/etcd/store/store.go
new file mode 100644
index 0000000..edf7f21
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/store.go
@@ -0,0 +1,791 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "encoding/json"
+ "fmt"
+ "path"
+ "strconv"
+ "strings"
+ "sync"
+ "time"
+
+ etcdErr "github.com/coreos/etcd/error"
+ "github.com/coreos/etcd/pkg/types"
+ "github.com/jonboulle/clockwork"
+)
+
+// The default version to set when the store is first initialized.
+const defaultVersion = 2
+
+var minExpireTime time.Time
+
+func init() {
+ minExpireTime, _ = time.Parse(time.RFC3339, "2000-01-01T00:00:00Z")
+}
+
+type Store interface {
+ Version() int
+ Index() uint64
+
+ Get(nodePath string, recursive, sorted bool) (*Event, error)
+ Set(nodePath string, dir bool, value string, expireOpts TTLOptionSet) (*Event, error)
+ Update(nodePath string, newValue string, expireOpts TTLOptionSet) (*Event, error)
+ Create(nodePath string, dir bool, value string, unique bool,
+ expireOpts TTLOptionSet) (*Event, error)
+ CompareAndSwap(nodePath string, prevValue string, prevIndex uint64,
+ value string, expireOpts TTLOptionSet) (*Event, error)
+ Delete(nodePath string, dir, recursive bool) (*Event, error)
+ CompareAndDelete(nodePath string, prevValue string, prevIndex uint64) (*Event, error)
+
+ Watch(prefix string, recursive, stream bool, sinceIndex uint64) (Watcher, error)
+
+ Save() ([]byte, error)
+ Recovery(state []byte) error
+
+ Clone() Store
+ SaveNoCopy() ([]byte, error)
+
+ JsonStats() []byte
+ DeleteExpiredKeys(cutoff time.Time)
+
+ HasTTLKeys() bool
+}
+
+type TTLOptionSet struct {
+ ExpireTime time.Time
+ Refresh bool
+}
+
+type store struct {
+ Root *node
+ WatcherHub *watcherHub
+ CurrentIndex uint64
+ Stats *Stats
+ CurrentVersion int
+ ttlKeyHeap *ttlKeyHeap // need to recovery manually
+ worldLock sync.RWMutex // stop the world lock
+ clock clockwork.Clock
+ readonlySet types.Set
+}
+
+// New creates a store where the given namespaces will be created as initial directories.
+func New(namespaces ...string) Store {
+ s := newStore(namespaces...)
+ s.clock = clockwork.NewRealClock()
+ return s
+}
+
+func newStore(namespaces ...string) *store {
+ s := new(store)
+ s.CurrentVersion = defaultVersion
+ s.Root = newDir(s, "/", s.CurrentIndex, nil, Permanent)
+ for _, namespace := range namespaces {
+ s.Root.Add(newDir(s, namespace, s.CurrentIndex, s.Root, Permanent))
+ }
+ s.Stats = newStats()
+ s.WatcherHub = newWatchHub(1000)
+ s.ttlKeyHeap = newTtlKeyHeap()
+ s.readonlySet = types.NewUnsafeSet(append(namespaces, "/")...)
+ return s
+}
+
+// Version retrieves current version of the store.
+func (s *store) Version() int {
+ return s.CurrentVersion
+}
+
+// Index retrieves the current index of the store.
+func (s *store) Index() uint64 {
+ s.worldLock.RLock()
+ defer s.worldLock.RUnlock()
+ return s.CurrentIndex
+}
+
+// Get returns a get event.
+// If recursive is true, it will return all the content under the node path.
+// If sorted is true, it will sort the content by keys.
+func (s *store) Get(nodePath string, recursive, sorted bool) (*Event, error) {
+ var err *etcdErr.Error
+
+ s.worldLock.RLock()
+ defer s.worldLock.RUnlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(GetSuccess)
+ if recursive {
+ reportReadSuccess(GetRecursive)
+ } else {
+ reportReadSuccess(Get)
+ }
+ return
+ }
+
+ s.Stats.Inc(GetFail)
+ if recursive {
+ reportReadFailure(GetRecursive)
+ } else {
+ reportReadFailure(Get)
+ }
+ }()
+
+ n, err := s.internalGet(nodePath)
+ if err != nil {
+ return nil, err
+ }
+
+ e := newEvent(Get, nodePath, n.ModifiedIndex, n.CreatedIndex)
+ e.EtcdIndex = s.CurrentIndex
+ e.Node.loadInternalNode(n, recursive, sorted, s.clock)
+
+ return e, nil
+}
+
+// Create creates the node at nodePath. Create will help to create intermediate directories with no ttl.
+// If the node has already existed, create will fail.
+// If any node on the path is a file, create will fail.
+func (s *store) Create(nodePath string, dir bool, value string, unique bool, expireOpts TTLOptionSet) (*Event, error) {
+ var err *etcdErr.Error
+
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(CreateSuccess)
+ reportWriteSuccess(Create)
+ return
+ }
+
+ s.Stats.Inc(CreateFail)
+ reportWriteFailure(Create)
+ }()
+
+ e, err := s.internalCreate(nodePath, dir, value, unique, false, expireOpts.ExpireTime, Create)
+ if err != nil {
+ return nil, err
+ }
+
+ e.EtcdIndex = s.CurrentIndex
+ s.WatcherHub.notify(e)
+
+ return e, nil
+}
+
+// Set creates or replace the node at nodePath.
+func (s *store) Set(nodePath string, dir bool, value string, expireOpts TTLOptionSet) (*Event, error) {
+ var err *etcdErr.Error
+
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(SetSuccess)
+ reportWriteSuccess(Set)
+ return
+ }
+
+ s.Stats.Inc(SetFail)
+ reportWriteFailure(Set)
+ }()
+
+ // Get prevNode value
+ n, getErr := s.internalGet(nodePath)
+ if getErr != nil && getErr.ErrorCode != etcdErr.EcodeKeyNotFound {
+ err = getErr
+ return nil, err
+ }
+
+ if expireOpts.Refresh {
+ if getErr != nil {
+ err = getErr
+ return nil, err
+ } else {
+ value = n.Value
+ }
+ }
+
+ // Set new value
+ e, err := s.internalCreate(nodePath, dir, value, false, true, expireOpts.ExpireTime, Set)
+ if err != nil {
+ return nil, err
+ }
+ e.EtcdIndex = s.CurrentIndex
+
+ // Put prevNode into event
+ if getErr == nil {
+ prev := newEvent(Get, nodePath, n.ModifiedIndex, n.CreatedIndex)
+ prev.Node.loadInternalNode(n, false, false, s.clock)
+ e.PrevNode = prev.Node
+ }
+
+ if !expireOpts.Refresh {
+ s.WatcherHub.notify(e)
+ } else {
+ e.SetRefresh()
+ s.WatcherHub.add(e)
+ }
+
+ return e, nil
+}
+
+// returns user-readable cause of failed comparison
+func getCompareFailCause(n *node, which int, prevValue string, prevIndex uint64) string {
+ switch which {
+ case CompareIndexNotMatch:
+ return fmt.Sprintf("[%v != %v]", prevIndex, n.ModifiedIndex)
+ case CompareValueNotMatch:
+ return fmt.Sprintf("[%v != %v]", prevValue, n.Value)
+ default:
+ return fmt.Sprintf("[%v != %v] [%v != %v]", prevValue, n.Value, prevIndex, n.ModifiedIndex)
+ }
+}
+
+func (s *store) CompareAndSwap(nodePath string, prevValue string, prevIndex uint64,
+ value string, expireOpts TTLOptionSet) (*Event, error) {
+
+ var err *etcdErr.Error
+
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(CompareAndSwapSuccess)
+ reportWriteSuccess(CompareAndSwap)
+ return
+ }
+
+ s.Stats.Inc(CompareAndSwapFail)
+ reportWriteFailure(CompareAndSwap)
+ }()
+
+ nodePath = path.Clean(path.Join("/", nodePath))
+ // we do not allow the user to change "/"
+ if s.readonlySet.Contains(nodePath) {
+ return nil, etcdErr.NewError(etcdErr.EcodeRootROnly, "/", s.CurrentIndex)
+ }
+
+ n, err := s.internalGet(nodePath)
+ if err != nil {
+ return nil, err
+ }
+ if n.IsDir() { // can only compare and swap file
+ err = etcdErr.NewError(etcdErr.EcodeNotFile, nodePath, s.CurrentIndex)
+ return nil, err
+ }
+
+ // If both of the prevValue and prevIndex are given, we will test both of them.
+ // Command will be executed, only if both of the tests are successful.
+ if ok, which := n.Compare(prevValue, prevIndex); !ok {
+ cause := getCompareFailCause(n, which, prevValue, prevIndex)
+ err = etcdErr.NewError(etcdErr.EcodeTestFailed, cause, s.CurrentIndex)
+ return nil, err
+ }
+
+ if expireOpts.Refresh {
+ value = n.Value
+ }
+
+ // update etcd index
+ s.CurrentIndex++
+
+ e := newEvent(CompareAndSwap, nodePath, s.CurrentIndex, n.CreatedIndex)
+ e.EtcdIndex = s.CurrentIndex
+ e.PrevNode = n.Repr(false, false, s.clock)
+ eNode := e.Node
+
+ // if test succeed, write the value
+ n.Write(value, s.CurrentIndex)
+ n.UpdateTTL(expireOpts.ExpireTime)
+
+ // copy the value for safety
+ valueCopy := value
+ eNode.Value = &valueCopy
+ eNode.Expiration, eNode.TTL = n.expirationAndTTL(s.clock)
+
+ if !expireOpts.Refresh {
+ s.WatcherHub.notify(e)
+ } else {
+ e.SetRefresh()
+ s.WatcherHub.add(e)
+ }
+
+ return e, nil
+}
+
+// Delete deletes the node at the given path.
+// If the node is a directory, recursive must be true to delete it.
+func (s *store) Delete(nodePath string, dir, recursive bool) (*Event, error) {
+ var err *etcdErr.Error
+
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(DeleteSuccess)
+ reportWriteSuccess(Delete)
+ return
+ }
+
+ s.Stats.Inc(DeleteFail)
+ reportWriteFailure(Delete)
+ }()
+
+ nodePath = path.Clean(path.Join("/", nodePath))
+ // we do not allow the user to change "/"
+ if s.readonlySet.Contains(nodePath) {
+ return nil, etcdErr.NewError(etcdErr.EcodeRootROnly, "/", s.CurrentIndex)
+ }
+
+ // recursive implies dir
+ if recursive {
+ dir = true
+ }
+
+ n, err := s.internalGet(nodePath)
+ if err != nil { // if the node does not exist, return error
+ return nil, err
+ }
+
+ nextIndex := s.CurrentIndex + 1
+ e := newEvent(Delete, nodePath, nextIndex, n.CreatedIndex)
+ e.EtcdIndex = nextIndex
+ e.PrevNode = n.Repr(false, false, s.clock)
+ eNode := e.Node
+
+ if n.IsDir() {
+ eNode.Dir = true
+ }
+
+ callback := func(path string) { // notify function
+ // notify the watchers with deleted set true
+ s.WatcherHub.notifyWatchers(e, path, true)
+ }
+
+ err = n.Remove(dir, recursive, callback)
+ if err != nil {
+ return nil, err
+ }
+
+ // update etcd index
+ s.CurrentIndex++
+
+ s.WatcherHub.notify(e)
+
+ return e, nil
+}
+
+func (s *store) CompareAndDelete(nodePath string, prevValue string, prevIndex uint64) (*Event, error) {
+ var err *etcdErr.Error
+
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(CompareAndDeleteSuccess)
+ reportWriteSuccess(CompareAndDelete)
+ return
+ }
+
+ s.Stats.Inc(CompareAndDeleteFail)
+ reportWriteFailure(CompareAndDelete)
+ }()
+
+ nodePath = path.Clean(path.Join("/", nodePath))
+
+ n, err := s.internalGet(nodePath)
+ if err != nil { // if the node does not exist, return error
+ return nil, err
+ }
+ if n.IsDir() { // can only compare and delete file
+ return nil, etcdErr.NewError(etcdErr.EcodeNotFile, nodePath, s.CurrentIndex)
+ }
+
+ // If both of the prevValue and prevIndex are given, we will test both of them.
+ // Command will be executed, only if both of the tests are successful.
+ if ok, which := n.Compare(prevValue, prevIndex); !ok {
+ cause := getCompareFailCause(n, which, prevValue, prevIndex)
+ return nil, etcdErr.NewError(etcdErr.EcodeTestFailed, cause, s.CurrentIndex)
+ }
+
+ // update etcd index
+ s.CurrentIndex++
+
+ e := newEvent(CompareAndDelete, nodePath, s.CurrentIndex, n.CreatedIndex)
+ e.EtcdIndex = s.CurrentIndex
+ e.PrevNode = n.Repr(false, false, s.clock)
+
+ callback := func(path string) { // notify function
+ // notify the watchers with deleted set true
+ s.WatcherHub.notifyWatchers(e, path, true)
+ }
+
+ err = n.Remove(false, false, callback)
+ if err != nil {
+ return nil, err
+ }
+
+ s.WatcherHub.notify(e)
+
+ return e, nil
+}
+
+func (s *store) Watch(key string, recursive, stream bool, sinceIndex uint64) (Watcher, error) {
+ s.worldLock.RLock()
+ defer s.worldLock.RUnlock()
+
+ key = path.Clean(path.Join("/", key))
+ if sinceIndex == 0 {
+ sinceIndex = s.CurrentIndex + 1
+ }
+ // WatcherHub does not know about the current index, so we need to pass it in
+ w, err := s.WatcherHub.watch(key, recursive, stream, sinceIndex, s.CurrentIndex)
+ if err != nil {
+ return nil, err
+ }
+
+ return w, nil
+}
+
+// walk walks all the nodePath and apply the walkFunc on each directory
+func (s *store) walk(nodePath string, walkFunc func(prev *node, component string) (*node, *etcdErr.Error)) (*node, *etcdErr.Error) {
+ components := strings.Split(nodePath, "/")
+
+ curr := s.Root
+ var err *etcdErr.Error
+
+ for i := 1; i < len(components); i++ {
+ if len(components[i]) == 0 { // ignore empty string
+ return curr, nil
+ }
+
+ curr, err = walkFunc(curr, components[i])
+ if err != nil {
+ return nil, err
+ }
+ }
+
+ return curr, nil
+}
+
+// Update updates the value/ttl of the node.
+// If the node is a file, the value and the ttl can be updated.
+// If the node is a directory, only the ttl can be updated.
+func (s *store) Update(nodePath string, newValue string, expireOpts TTLOptionSet) (*Event, error) {
+ var err *etcdErr.Error
+
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ defer func() {
+ if err == nil {
+ s.Stats.Inc(UpdateSuccess)
+ reportWriteSuccess(Update)
+ return
+ }
+
+ s.Stats.Inc(UpdateFail)
+ reportWriteFailure(Update)
+ }()
+
+ nodePath = path.Clean(path.Join("/", nodePath))
+ // we do not allow the user to change "/"
+ if s.readonlySet.Contains(nodePath) {
+ return nil, etcdErr.NewError(etcdErr.EcodeRootROnly, "/", s.CurrentIndex)
+ }
+
+ currIndex, nextIndex := s.CurrentIndex, s.CurrentIndex+1
+
+ n, err := s.internalGet(nodePath)
+ if err != nil { // if the node does not exist, return error
+ return nil, err
+ }
+ if n.IsDir() && len(newValue) != 0 {
+ // if the node is a directory, we cannot update value to non-empty
+ return nil, etcdErr.NewError(etcdErr.EcodeNotFile, nodePath, currIndex)
+ }
+
+ if expireOpts.Refresh {
+ newValue = n.Value
+ }
+
+ e := newEvent(Update, nodePath, nextIndex, n.CreatedIndex)
+ e.EtcdIndex = nextIndex
+ e.PrevNode = n.Repr(false, false, s.clock)
+ eNode := e.Node
+
+ n.Write(newValue, nextIndex)
+
+ if n.IsDir() {
+ eNode.Dir = true
+ } else {
+ // copy the value for safety
+ newValueCopy := newValue
+ eNode.Value = &newValueCopy
+ }
+
+ // update ttl
+ n.UpdateTTL(expireOpts.ExpireTime)
+
+ eNode.Expiration, eNode.TTL = n.expirationAndTTL(s.clock)
+
+ if !expireOpts.Refresh {
+ s.WatcherHub.notify(e)
+ } else {
+ e.SetRefresh()
+ s.WatcherHub.add(e)
+ }
+
+ s.CurrentIndex = nextIndex
+
+ return e, nil
+}
+
+func (s *store) internalCreate(nodePath string, dir bool, value string, unique, replace bool,
+ expireTime time.Time, action string) (*Event, *etcdErr.Error) {
+
+ currIndex, nextIndex := s.CurrentIndex, s.CurrentIndex+1
+
+ if unique { // append unique item under the node path
+ nodePath += "/" + fmt.Sprintf("%020s", strconv.FormatUint(nextIndex, 10))
+ }
+
+ nodePath = path.Clean(path.Join("/", nodePath))
+
+ // we do not allow the user to change "/"
+ if s.readonlySet.Contains(nodePath) {
+ return nil, etcdErr.NewError(etcdErr.EcodeRootROnly, "/", currIndex)
+ }
+
+ // Assume expire times that are way in the past are
+ // This can occur when the time is serialized to JS
+ if expireTime.Before(minExpireTime) {
+ expireTime = Permanent
+ }
+
+ dirName, nodeName := path.Split(nodePath)
+
+ // walk through the nodePath, create dirs and get the last directory node
+ d, err := s.walk(dirName, s.checkDir)
+
+ if err != nil {
+ s.Stats.Inc(SetFail)
+ reportWriteFailure(action)
+ err.Index = currIndex
+ return nil, err
+ }
+
+ e := newEvent(action, nodePath, nextIndex, nextIndex)
+ eNode := e.Node
+
+ n, _ := d.GetChild(nodeName)
+
+ // force will try to replace an existing file
+ if n != nil {
+ if replace {
+ if n.IsDir() {
+ return nil, etcdErr.NewError(etcdErr.EcodeNotFile, nodePath, currIndex)
+ }
+ e.PrevNode = n.Repr(false, false, s.clock)
+
+ n.Remove(false, false, nil)
+ } else {
+ return nil, etcdErr.NewError(etcdErr.EcodeNodeExist, nodePath, currIndex)
+ }
+ }
+
+ if !dir { // create file
+ // copy the value for safety
+ valueCopy := value
+ eNode.Value = &valueCopy
+
+ n = newKV(s, nodePath, value, nextIndex, d, expireTime)
+
+ } else { // create directory
+ eNode.Dir = true
+
+ n = newDir(s, nodePath, nextIndex, d, expireTime)
+ }
+
+ // we are sure d is a directory and does not have the children with name n.Name
+ d.Add(n)
+
+ // node with TTL
+ if !n.IsPermanent() {
+ s.ttlKeyHeap.push(n)
+
+ eNode.Expiration, eNode.TTL = n.expirationAndTTL(s.clock)
+ }
+
+ s.CurrentIndex = nextIndex
+
+ return e, nil
+}
+
+// InternalGet gets the node of the given nodePath.
+func (s *store) internalGet(nodePath string) (*node, *etcdErr.Error) {
+ nodePath = path.Clean(path.Join("/", nodePath))
+
+ walkFunc := func(parent *node, name string) (*node, *etcdErr.Error) {
+
+ if !parent.IsDir() {
+ err := etcdErr.NewError(etcdErr.EcodeNotDir, parent.Path, s.CurrentIndex)
+ return nil, err
+ }
+
+ child, ok := parent.Children[name]
+ if ok {
+ return child, nil
+ }
+
+ return nil, etcdErr.NewError(etcdErr.EcodeKeyNotFound, path.Join(parent.Path, name), s.CurrentIndex)
+ }
+
+ f, err := s.walk(nodePath, walkFunc)
+
+ if err != nil {
+ return nil, err
+ }
+ return f, nil
+}
+
+// DeleteExpiredKeys will delete all expired keys
+func (s *store) DeleteExpiredKeys(cutoff time.Time) {
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+
+ for {
+ node := s.ttlKeyHeap.top()
+ if node == nil || node.ExpireTime.After(cutoff) {
+ break
+ }
+
+ s.CurrentIndex++
+ e := newEvent(Expire, node.Path, s.CurrentIndex, node.CreatedIndex)
+ e.EtcdIndex = s.CurrentIndex
+ e.PrevNode = node.Repr(false, false, s.clock)
+ if node.IsDir() {
+ e.Node.Dir = true
+ }
+
+ callback := func(path string) { // notify function
+ // notify the watchers with deleted set true
+ s.WatcherHub.notifyWatchers(e, path, true)
+ }
+
+ s.ttlKeyHeap.pop()
+ node.Remove(true, true, callback)
+
+ reportExpiredKey()
+ s.Stats.Inc(ExpireCount)
+
+ s.WatcherHub.notify(e)
+ }
+
+}
+
+// checkDir will check whether the component is a directory under parent node.
+// If it is a directory, this function will return the pointer to that node.
+// If it does not exist, this function will create a new directory and return the pointer to that node.
+// If it is a file, this function will return error.
+func (s *store) checkDir(parent *node, dirName string) (*node, *etcdErr.Error) {
+ node, ok := parent.Children[dirName]
+
+ if ok {
+ if node.IsDir() {
+ return node, nil
+ }
+
+ return nil, etcdErr.NewError(etcdErr.EcodeNotDir, node.Path, s.CurrentIndex)
+ }
+
+ n := newDir(s, path.Join(parent.Path, dirName), s.CurrentIndex+1, parent, Permanent)
+
+ parent.Children[dirName] = n
+
+ return n, nil
+}
+
+// Save saves the static state of the store system.
+// It will not be able to save the state of watchers.
+// It will not save the parent field of the node. Or there will
+// be cyclic dependencies issue for the json package.
+func (s *store) Save() ([]byte, error) {
+ b, err := json.Marshal(s.Clone())
+ if err != nil {
+ return nil, err
+ }
+
+ return b, nil
+}
+
+func (s *store) SaveNoCopy() ([]byte, error) {
+ b, err := json.Marshal(s)
+ if err != nil {
+ return nil, err
+ }
+
+ return b, nil
+}
+
+func (s *store) Clone() Store {
+ s.worldLock.Lock()
+
+ clonedStore := newStore()
+ clonedStore.CurrentIndex = s.CurrentIndex
+ clonedStore.Root = s.Root.Clone()
+ clonedStore.WatcherHub = s.WatcherHub.clone()
+ clonedStore.Stats = s.Stats.clone()
+ clonedStore.CurrentVersion = s.CurrentVersion
+
+ s.worldLock.Unlock()
+ return clonedStore
+}
+
+// Recovery recovers the store system from a static state
+// It needs to recover the parent field of the nodes.
+// It needs to delete the expired nodes since the saved time and also
+// needs to create monitoring go routines.
+func (s *store) Recovery(state []byte) error {
+ s.worldLock.Lock()
+ defer s.worldLock.Unlock()
+ err := json.Unmarshal(state, s)
+
+ if err != nil {
+ return err
+ }
+
+ s.ttlKeyHeap = newTtlKeyHeap()
+
+ s.Root.recoverAndclean()
+ return nil
+}
+
+func (s *store) JsonStats() []byte {
+ s.Stats.Watchers = uint64(s.WatcherHub.count)
+ return s.Stats.toJson()
+}
+
+func (s *store) HasTTLKeys() bool {
+ s.worldLock.RLock()
+ defer s.worldLock.RUnlock()
+ return s.ttlKeyHeap.Len() != 0
+}
diff --git a/vendor/github.com/coreos/etcd/store/ttl_key_heap.go b/vendor/github.com/coreos/etcd/store/ttl_key_heap.go
new file mode 100644
index 0000000..21ae9b7
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/ttl_key_heap.go
@@ -0,0 +1,99 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "container/heap"
+)
+
+// An TTLKeyHeap is a min-heap of TTLKeys order by expiration time
+type ttlKeyHeap struct {
+ array []*node
+ keyMap map[*node]int
+}
+
+func newTtlKeyHeap() *ttlKeyHeap {
+ h := &ttlKeyHeap{keyMap: make(map[*node]int)}
+ heap.Init(h)
+ return h
+}
+
+func (h ttlKeyHeap) Len() int {
+ return len(h.array)
+}
+
+func (h ttlKeyHeap) Less(i, j int) bool {
+ return h.array[i].ExpireTime.Before(h.array[j].ExpireTime)
+}
+
+func (h ttlKeyHeap) Swap(i, j int) {
+ // swap node
+ h.array[i], h.array[j] = h.array[j], h.array[i]
+
+ // update map
+ h.keyMap[h.array[i]] = i
+ h.keyMap[h.array[j]] = j
+}
+
+func (h *ttlKeyHeap) Push(x interface{}) {
+ n, _ := x.(*node)
+ h.keyMap[n] = len(h.array)
+ h.array = append(h.array, n)
+}
+
+func (h *ttlKeyHeap) Pop() interface{} {
+ old := h.array
+ n := len(old)
+ x := old[n-1]
+ // Set slice element to nil, so GC can recycle the node.
+ // This is due to golang GC doesn't support partial recycling:
+ // https://github.com/golang/go/issues/9618
+ old[n-1] = nil
+ h.array = old[0 : n-1]
+ delete(h.keyMap, x)
+ return x
+}
+
+func (h *ttlKeyHeap) top() *node {
+ if h.Len() != 0 {
+ return h.array[0]
+ }
+ return nil
+}
+
+func (h *ttlKeyHeap) pop() *node {
+ x := heap.Pop(h)
+ n, _ := x.(*node)
+ return n
+}
+
+func (h *ttlKeyHeap) push(x interface{}) {
+ heap.Push(h, x)
+}
+
+func (h *ttlKeyHeap) update(n *node) {
+ index, ok := h.keyMap[n]
+ if ok {
+ heap.Remove(h, index)
+ heap.Push(h, n)
+ }
+}
+
+func (h *ttlKeyHeap) remove(n *node) {
+ index, ok := h.keyMap[n]
+ if ok {
+ heap.Remove(h, index)
+ }
+}
diff --git a/vendor/github.com/coreos/etcd/store/watcher.go b/vendor/github.com/coreos/etcd/store/watcher.go
new file mode 100644
index 0000000..a236ec7
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/watcher.go
@@ -0,0 +1,95 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+type Watcher interface {
+ EventChan() chan *Event
+ StartIndex() uint64 // The EtcdIndex at which the Watcher was created
+ Remove()
+}
+
+type watcher struct {
+ eventChan chan *Event
+ stream bool
+ recursive bool
+ sinceIndex uint64
+ startIndex uint64
+ hub *watcherHub
+ removed bool
+ remove func()
+}
+
+func (w *watcher) EventChan() chan *Event {
+ return w.eventChan
+}
+
+func (w *watcher) StartIndex() uint64 {
+ return w.startIndex
+}
+
+// notify function notifies the watcher. If the watcher interests in the given path,
+// the function will return true.
+func (w *watcher) notify(e *Event, originalPath bool, deleted bool) bool {
+ // watcher is interested the path in three cases and under one condition
+ // the condition is that the event happens after the watcher's sinceIndex
+
+ // 1. the path at which the event happens is the path the watcher is watching at.
+ // For example if the watcher is watching at "/foo" and the event happens at "/foo",
+ // the watcher must be interested in that event.
+
+ // 2. the watcher is a recursive watcher, it interests in the event happens after
+ // its watching path. For example if watcher A watches at "/foo" and it is a recursive
+ // one, it will interest in the event happens at "/foo/bar".
+
+ // 3. when we delete a directory, we need to force notify all the watchers who watches
+ // at the file we need to delete.
+ // For example a watcher is watching at "/foo/bar". And we deletes "/foo". The watcher
+ // should get notified even if "/foo" is not the path it is watching.
+ if (w.recursive || originalPath || deleted) && e.Index() >= w.sinceIndex {
+ // We cannot block here if the eventChan capacity is full, otherwise
+ // etcd will hang. eventChan capacity is full when the rate of
+ // notifications are higher than our send rate.
+ // If this happens, we close the channel.
+ select {
+ case w.eventChan <- e:
+ default:
+ // We have missed a notification. Remove the watcher.
+ // Removing the watcher also closes the eventChan.
+ w.remove()
+ }
+ return true
+ }
+ return false
+}
+
+// Remove removes the watcher from watcherHub
+// The actual remove function is guaranteed to only be executed once
+func (w *watcher) Remove() {
+ w.hub.mutex.Lock()
+ defer w.hub.mutex.Unlock()
+
+ close(w.eventChan)
+ if w.remove != nil {
+ w.remove()
+ }
+}
+
+// nopWatcher is a watcher that receives nothing, always blocking.
+type nopWatcher struct{}
+
+func NewNopWatcher() Watcher { return &nopWatcher{} }
+func (w *nopWatcher) EventChan() chan *Event { return nil }
+func (w *nopWatcher) StartIndex() uint64 { return 0 }
+func (w *nopWatcher) Remove() {}
diff --git a/vendor/github.com/coreos/etcd/store/watcher_hub.go b/vendor/github.com/coreos/etcd/store/watcher_hub.go
new file mode 100644
index 0000000..13c23e3
--- /dev/null
+++ b/vendor/github.com/coreos/etcd/store/watcher_hub.go
@@ -0,0 +1,200 @@
+// Copyright 2015 The etcd Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package store
+
+import (
+ "container/list"
+ "path"
+ "strings"
+ "sync"
+ "sync/atomic"
+
+ etcdErr "github.com/coreos/etcd/error"
+)
+
+// A watcherHub contains all subscribed watchers
+// watchers is a map with watched path as key and watcher as value
+// EventHistory keeps the old events for watcherHub. It is used to help
+// watcher to get a continuous event history. Or a watcher might miss the
+// event happens between the end of the first watch command and the start
+// of the second command.
+type watcherHub struct {
+ // count must be the first element to keep 64-bit alignment for atomic
+ // access
+
+ count int64 // current number of watchers.
+
+ mutex sync.Mutex
+ watchers map[string]*list.List
+ EventHistory *EventHistory
+}
+
+// newWatchHub creates a watcherHub. The capacity determines how many events we will
+// keep in the eventHistory.
+// Typically, we only need to keep a small size of history[smaller than 20K].
+// Ideally, it should smaller than 20K/s[max throughput] * 2 * 50ms[RTT] = 2000
+func newWatchHub(capacity int) *watcherHub {
+ return &watcherHub{
+ watchers: make(map[string]*list.List),
+ EventHistory: newEventHistory(capacity),
+ }
+}
+
+// Watch function returns a Watcher.
+// If recursive is true, the first change after index under key will be sent to the event channel of the watcher.
+// If recursive is false, the first change after index at key will be sent to the event channel of the watcher.
+// If index is zero, watch will start from the current index + 1.
+func (wh *watcherHub) watch(key string, recursive, stream bool, index, storeIndex uint64) (Watcher, *etcdErr.Error) {
+ reportWatchRequest()
+ event, err := wh.EventHistory.scan(key, recursive, index)
+
+ if err != nil {
+ err.Index = storeIndex
+ return nil, err
+ }
+
+ w := &watcher{
+ eventChan: make(chan *Event, 100), // use a buffered channel
+ recursive: recursive,
+ stream: stream,
+ sinceIndex: index,
+ startIndex: storeIndex,
+ hub: wh,
+ }
+
+ wh.mutex.Lock()
+ defer wh.mutex.Unlock()
+ // If the event exists in the known history, append the EtcdIndex and return immediately
+ if event != nil {
+ ne := event.Clone()
+ ne.EtcdIndex = storeIndex
+ w.eventChan <- ne
+ return w, nil
+ }
+
+ l, ok := wh.watchers[key]
+
+ var elem *list.Element
+
+ if ok { // add the new watcher to the back of the list
+ elem = l.PushBack(w)
+ } else { // create a new list and add the new watcher
+ l = list.New()
+ elem = l.PushBack(w)
+ wh.watchers[key] = l
+ }
+
+ w.remove = func() {
+ if w.removed { // avoid removing it twice
+ return
+ }
+ w.removed = true
+ l.Remove(elem)
+ atomic.AddInt64(&wh.count, -1)
+ reportWatcherRemoved()
+ if l.Len() == 0 {
+ delete(wh.watchers, key)
+ }
+ }
+
+ atomic.AddInt64(&wh.count, 1)
+ reportWatcherAdded()
+
+ return w, nil
+}
+
+func (wh *watcherHub) add(e *Event) {
+ wh.EventHistory.addEvent(e)
+}
+
+// notify function accepts an event and notify to the watchers.
+func (wh *watcherHub) notify(e *Event) {
+ e = wh.EventHistory.addEvent(e) // add event into the eventHistory
+
+ segments := strings.Split(e.Node.Key, "/")
+
+ currPath := "/"
+
+ // walk through all the segments of the path and notify the watchers
+ // if the path is "/foo/bar", it will notify watchers with path "/",
+ // "/foo" and "/foo/bar"
+
+ for _, segment := range segments {
+ currPath = path.Join(currPath, segment)
+ // notify the watchers who interests in the changes of current path
+ wh.notifyWatchers(e, currPath, false)
+ }
+}
+
+func (wh *watcherHub) notifyWatchers(e *Event, nodePath string, deleted bool) {
+ wh.mutex.Lock()
+ defer wh.mutex.Unlock()
+
+ l, ok := wh.watchers[nodePath]
+ if ok {
+ curr := l.Front()
+
+ for curr != nil {
+ next := curr.Next() // save reference to the next one in the list
+
+ w, _ := curr.Value.(*watcher)
+
+ originalPath := (e.Node.Key == nodePath)
+ if (originalPath || !isHidden(nodePath, e.Node.Key)) && w.notify(e, originalPath, deleted) {
+ if !w.stream { // do not remove the stream watcher
+ // if we successfully notify a watcher
+ // we need to remove the watcher from the list
+ // and decrease the counter
+ w.removed = true
+ l.Remove(curr)
+ atomic.AddInt64(&wh.count, -1)
+ reportWatcherRemoved()
+ }
+ }
+
+ curr = next // update current to the next element in the list
+ }
+
+ if l.Len() == 0 {
+ // if we have notified all watcher in the list
+ // we can delete the list
+ delete(wh.watchers, nodePath)
+ }
+ }
+}
+
+// clone function clones the watcherHub and return the cloned one.
+// only clone the static content. do not clone the current watchers.
+func (wh *watcherHub) clone() *watcherHub {
+ clonedHistory := wh.EventHistory.clone()
+
+ return &watcherHub{
+ EventHistory: clonedHistory,
+ }
+}
+
+// isHidden checks to see if key path is considered hidden to watch path i.e. the
+// last element is hidden or it's within a hidden directory
+func isHidden(watchPath, keyPath string) bool {
+ // When deleting a directory, watchPath might be deeper than the actual keyPath
+ // For example, when deleting /foo we also need to notify watchers on /foo/bar.
+ if len(watchPath) > len(keyPath) {
+ return false
+ }
+ // if watch path is just a "/", after path will start without "/"
+ // add a "/" to deal with the special case when watchPath is "/"
+ afterPath := path.Clean("/" + keyPath[len(watchPath):])
+ return strings.Contains(afterPath, "/_")
+}