/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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 org.apache.ignite.internal.processors.cache;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Helper class to acquire java level locks on unordered set of entries and avoid deadlocks.
 */
public class LockedEntriesInfo {
    /** Deadlock detection timeout in milliseconds. */
    private static final long DEADLOCK_DETECTION_TIMEOUT = 500L;

    /** Locked entries info for each thread. */
    private final Map<Long, LockedEntries> lockedEntriesPerThread = new ConcurrentHashMap<>();

    /**
     * Attempt to lock all provided entries avoiding deadlocks.
     *
     * @param entries Entries to lock.
     * @return {@code True} if entries were successfully locked, {@code false} if possible deadlock detected or
     *      some entries are obsolete (lock attempt should be retried in this case).
     */
    public boolean tryLockEntries(GridCacheEntryEx[] entries) {
        long threadId = Thread.currentThread().getId();

        LockedEntries lockedEntries = new LockedEntries(entries);

        lockedEntriesPerThread.put(threadId, lockedEntries);

        boolean wasInterrupted = false;

        try {
            for (int i = 0; i < entries.length; i++) {
                GridCacheEntryEx entry = entries[i];

                if (entry == null)
                    continue;

                boolean retry = false;

                while (true) {
                    if (entry.tryLockEntry(DEADLOCK_DETECTION_TIMEOUT))
                        break; // Successfully locked.
                    else {
                        wasInterrupted |= Thread.interrupted(); // Clear thread interruption flag.

                        if (hasLockCollisions(entry, lockedEntries)) {
                            // Possible deadlock detected, unlock all locked entries and retry again.
                            retry = true;

                            break;
                        }
                        // Possible deadlock not detected, just retry lock on current entry.
                    }
                }

                if (!retry && entry.obsolete()) {
                    entry.unlockEntry();

                    retry = true;
                }

                if (retry) {
                    lockedEntries.lockedIdx = -1;

                    // Unlock all previously locked.
                    for (int j = 0; j < i; j++) {
                        if (entries[j] != null)
                            entries[j].unlockEntry();
                    }

                    return false;
                }

                lockedEntries.lockedIdx = i;
            }

            return true;
        }
        finally {
            if (wasInterrupted)
                Thread.currentThread().interrupt();

            // Already acuired all locks or released all locks here, deadlock is not possible by this thread anymore,
            // can safely delete locks information.
            lockedEntriesPerThread.remove(threadId);
        }
    }

    /**
     * @param entry Entry.
     * @param curLockedEntries Current locked entries info.
     * @return {@code True} if another thread holds lock for this entry and started to lock entries earlier.
     */
    private boolean hasLockCollisions(GridCacheEntryEx entry, LockedEntries curLockedEntries) {
        for (Map.Entry<Long, LockedEntries> other : lockedEntriesPerThread.entrySet()) {
            LockedEntries otherLockedEntries = other.getValue();

            if (otherLockedEntries == curLockedEntries || otherLockedEntries.ts > curLockedEntries.ts)
                // Skip current thread and threads started to lock after the current thread.
                continue;

            GridCacheEntryEx[] otherThreadLocks = otherLockedEntries.entries;

            int otherThreadLockedIdx = otherLockedEntries.lockedIdx;

            // Visibility guarantees provided by volatile lockedIdx field.
            for (int i = 0; i <= otherThreadLockedIdx; i++) {
                if (otherThreadLocks[i] == entry)
                    return true;
            }
        }

        return false;
    }

    /** Per-thread locked entries info. */
    private static class LockedEntries {
        /** Timestamp of lock. */
        private final long ts = System.nanoTime();

        /** Entries to lock. */
        private final GridCacheEntryEx[] entries;

        /** Current locked entry index. */
        private volatile int lockedIdx = -1;

        /** */
        private LockedEntries(GridCacheEntryEx[] entries) {
            this.entries = entries;
        }
    }
}